Leetcode 05 java
206. 反转链表
1 题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
我的想法：
乱想的思路。其实是根据之前判断回文和翻转链表，我觉得可以用上双指针吧，或者数组。
先把链表存在数组里面，然后用循环语句反序依次输出。存储数组的循环条件用指针不为空作为限制，反序输出就用for循环？
按照【数组反转】思想可以这样写：
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode reverseList(ListNode head) {// 如果链表为空或只有一个节点，直接返回if (head == null || head.next == null) {return head;}// 将链表节点存入数组java.util.ArrayList<ListNode> nodes = new java.util.ArrayList<>();ListNode current = head;while (current != null) {nodes.add(current);current = current.next;}// 反序连接节点for (int i = nodes.size() - 1; i > 0; i--) {nodes.get(i).next = nodes.get(i - 1);}// 原头节点变为尾节点，next 需置为 nullnodes.get(0).next = null;// 返回新的头节点return nodes.get(nodes.size() - 1);}
}代码说明：
- 链表节点定义：
ListNode类表示链表中的节点，包含整数值val和指向下一个节点的引用next。 - 特殊情况处理：当链表为空或只有一个节点时直接返回。
- 存储节点到数组：遍历链表，将每个节点存入
ArrayList中。 - 反序连接节点：从数组的最后一个节点开始，依次将每个节点的
next指向前一个节点。 - 处理尾节点：原链表的头节点（即数组的第一个元素）变为尾节点，其
next设为null。 - 返回新头节点：数组的最后一个元素即为反转后的链表头节点。
这种方法的时间复杂度是 O (n)，空间复杂度也是 O (n)，因为需要额外的数组来存储节点。
2 区分 反转节点的值 和 反转链表的节点（结构）
1. 错误解法：仅反转节点的值（未改变链表结构）
java
// 仅反转节点的值，链表的指针结构未变
public ListNode reverseList(ListNode head) {// 步骤1：收集所有节点的值List<Integer> values = new ArrayList<>();ListNode curr = head;while (curr != null) {values.add(curr.val); // 只存值，不存节点curr = curr.next;}// 步骤2：反转值的顺序（例如 [1,2,3] → [3,2,1]）Collections.reverse(values);// 步骤3：将反转后的值重新赋给原链表的节点curr = head;int index = 0;while (curr != null) {curr.val = values.get(index++); // 只改值，不改指针curr = curr.next;}return head; // 返回原头节点（链表结构没变）
}
核心特点：
- 操作对象：只处理节点的
val（值），不碰next（指针）。 - 链表结构：原链表的指针方向完全不变。例如原链表是
1→2→3，处理后指针仍为1→2→3，但节点值变成了3,2,1（即3→2→1的值，但指针还是1在前，3在后）。 - 本质：相当于 “换汤不换药”，只是把节点里的数据换了顺序，链表的连接关系（结构）没动。
2. 正确解法：反转链表的节点（修改结构）
java
// 反转链表的节点（修改指针结构），你的数组解法属于此类
public ListNode reverseList(ListNode head) {// 步骤1：收集所有节点（存的是节点本身，不是值）List<ListNode> nodes = new ArrayList<>();ListNode curr = head;while (curr != null) {nodes.add(curr); // 存节点引用，后续要改它们的指针curr = curr.next;}// 步骤2：修改节点的next指针，反序连接for (int i = nodes.size() - 1; i > 0; i--) {nodes.get(i).next = nodes.get(i - 1); // 后一个节点指向前一个}// 步骤3：原头节点变尾节点，next置空（避免环）if (!nodes.isEmpty()) {nodes.get(0).next = null;}// 步骤4：返回新头节点（原链表的最后一个节点）return nodes.isEmpty() ? null : nodes.get(nodes.size() - 1);
}
核心特点：
- 操作对象：主要修改节点的
next指针（连接关系），节点的val完全不变。 - 链表结构：彻底改变指针方向。例如原链表
1→2→3，处理后指针变为3→2→1，节点值还是1,2,3（即结构上3在前，1在后，值和节点一一对应）。 - 本质：相当于 “换骨不换汤”，节点本身没变（值不变），但它们的连接顺序（结构）完全反转了。
关键对比表
| 维度 | 仅反转节点的值（错误） | 反转链表的节点（正确） |
|---|---|---|
| 操作的是 | 节点的 val（数据） | 节点的 next（指针 / 结构） |
| 链表指针方向 | 不变 | 完全反转 |
| 节点本身是否移动 | 不移动（位置不变，值变） | 位置反转（通过指针重新连接） |
| 举例（原链表 1→2→3） | 结果：1→2→3（指针），值 3,2,1 | 结果：3→2→1（指针），值 1,2,3 |
总结
- 题目要求 “反转链表”，本质是反转节点的连接顺序（结构），即让原本在后的节点跑到前面，指针方向反过来。
- 仅反转节点的值是 “假反转”，因为链表的结构（谁在前谁在后）没变，只是数据换了，不符合题意。
- 你的数组解法属于 “反转节点（结构）”，是正确的，只是空间复杂度比官方迭代法高。
3 官方迭代（双指针）题解
class Solution {public ListNode reverseList(ListNode head) {// 初始化前驱节点为 null，用于作为反转后的链表尾部ListNode prev = null;// 初始化当前节点为头节点，从链表头部开始处理ListNode curr = head;// 循环遍历链表，直到当前节点为空（即到达原链表尾部之后）while (curr != null) {// 1. 临时保存当前节点的下一个节点// 防止在反转指针后丢失后续链表ListNode next = curr.next;// 2. 反转当前节点的指针方向// 将当前节点的 next 指向前驱节点（完成局部反转）curr.next = prev;// 3. 前驱节点向前移动一步// 当前节点成为新的前驱节点，为处理下一个节点做准备prev = curr;// 4. 当前节点向前移动一步// 继续处理原链表的下一个节点curr = next;}// 循环结束时，curr 为 null，prev 指向原链表的最后一个节点// 即反转后的新链表的头节点，返回该节点return prev;}
}先明确目标：什么是 “反转链表”？
假设原链表是 1 → 2 → 3 → null（箭头表示 next 指针），反转后要变成 3 → 2 → 1 → null。
简单说：每个节点的 next 指针，从 “指向后一个节点” 变成 “指向前一个节点”。
核心思路：用两个指针 “原地反转”
不需要额外创建新节点，也不需要数组存储，直接在原链表上修改指针方向。
用两个指针：prev（前一个节点）和 curr（当前节点），从链表头开始，一步步把每个节点的指针 “掉个头”。
步骤拆解（配动态演示）
咱们用具体例子 1 → 2 → 3 → null 来演示，每一步都画出来，保证看得懂！
初始状态
java
ListNode prev = null; // 一开始，“前一个节点”不存在，所以是null
ListNode curr = head; // “当前节点”从链表头（1）开始
对应图示：
plaintext
prev: null
curr: 1 → 2 → 3 → null
第一步：处理第一个节点（1）
循环条件：curr != null（当前节点存在，就继续处理）。
-
保存下一个节点：
ListNode next = curr.next;
作用：防止修改curr.next后，找不到后面的节点（2）。
此时next指向 2：plaintext
prev: null curr: 1 → 2 → 3 → null next: 2 → 3 → null （临时保存） -
反转当前节点的指针：
curr.next = prev;
原来1.next指向 2，现在让它指向prev（也就是null）。
此时 1 的指针反转完成：1 → nullplaintext
prev: null curr: 1 → null （指针已反转） next: 2 → 3 → null （暂时没动） -
移动指针，准备处理下一个节点：
prev = curr;（prev挪到当前节点 1，因为下一次要让 2 指向 1）curr = next;（curr挪到下一个节点 2，准备处理它）
此时指针位置：
plaintext
prev: 1 → null curr: 2 → 3 → null next: 2 → 3 → null （已经没用了，下次循环会重新赋值）
第二步：处理第二个节点（2）
循环继续（curr 现在是 2，不为 null）。
-
保存下一个节点：
ListNode next = curr.next;
现在next指向 3：plaintext
prev: 1 → null curr: 2 → 3 → null next: 3 → null （临时保存） -
反转当前节点的指针：
curr.next = prev;
原来2.next指向 3，现在让它指向prev（也就是 1）。
此时 2 的指针反转完成：2 → 1 → nullplaintext
prev: 1 → null curr: 2 → 1 → null （指针已反转） next: 3 → null （暂时没动） -
移动指针，准备处理下一个节点：
prev = curr;（prev挪到当前节点 2，下一次要让 3 指向 2）curr = next;（curr挪到下一个节点 3）
此时指针位置：
plaintext
prev: 2 → 1 → null curr: 3 → null
第三步：处理第三个节点（3）
循环继续（curr 现在是 3，不为 null）。
-
保存下一个节点：
ListNode next = curr.next;
现在next指向null（因为 3 是最后一个节点）：plaintext
prev: 2 → 1 → null curr: 3 → null next: null （临时保存） -
反转当前节点的指针：
curr.next = prev;
原来3.next指向null，现在让它指向prev（也就是 2）。
此时 3 的指针反转完成：3 → 2 → 1 → nullplaintext
prev: 2 → 1 → null curr: 3 → 2 → 1 → null （指针已反转） next: null （暂时没动） -
移动指针，准备处理下一个节点：
prev = curr;（prev挪到当前节点 3）curr = next;（curr挪到null）
此时指针位置：
plaintext
prev: 3 → 2 → 1 → null curr: null
循环结束，返回结果
当 curr == null 时，循环停止。此时 prev 指向的就是反转后链表的头节点（3），返回 prev 即可。
代码逐行翻译成人话
java
public ListNode reverseList(ListNode head) {// 1. 初始化前一个节点为null（反转后第一个节点的next要指向null）ListNode prev = null;// 2. 初始化当前节点为头节点（从第一个节点开始处理）ListNode curr = head;// 3. 只要当前节点不为null，就继续处理while (curr != null) {// 3.1 先把当前节点的下一个节点记下来（怕丢了）ListNode next = curr.next;// 3.2 关键：让当前节点的next指向前一个节点（反转指针）curr.next = prev;// 3.3 前一个节点往前挪一步（变成当前节点）prev = curr;// 3.4 当前节点往前挪一步（变成之前记下的下一个节点）curr = next;}// 4. 循环结束时，prev就是新的头节点return prev;
}
为什么这个方法能成？
- 每一步只关心 “当前节点”：不用想太远，只需要把当前节点的指针扭过来，指向它原来的前一个节点。
- 指针移动有规律：处理完一个节点后，
prev和curr依次往后挪，不会乱。 - 空间效率高：只用到 3 个额外指针（
prev、curr、next），空间复杂度 O (1)，比用数组的方法省内存。
总结：记住这 4 句话
- 用
prev记住 “前一个节点”，初始为null。 - 用
curr遍历链表，从head开始。 - 每次循环：先存
next，再扭curr.next到prev，最后挪prev和curr。 - 循环结束，
prev就是反转后的头。
4 头插法（“插头法”）
“插头法” 也是反转链表的一种经典思路，本质上是通过 “头插法” 将节点逐个插入到新链表的头部，从而实现反转。
插头法核心思路
想象有一个 “新链表”（初始为空），我们从原链表的头部开始，把每个节点 “拔下来”，再 “插” 到新链表的头部。重复这个过程，直到原链表的节点全部插完，新链表就是反转后的结果。
举个例子：
原链表：1 → 2 → 3 → null
- 先把
1插到新链表头部 → 新链表：1 → null - 再把
2插到新链表头部 → 新链表：2 → 1 → null - 最后把
3插到新链表头部 → 新链表：3 → 2 → 1 → null
步骤拆解（配动态演示）
初始状态
- 原链表：
1 → 2 → 3 → null - 定义
newHead表示新链表的头部（初始为null，因为新链表一开始是空的） - 定义
curr表示当前要 “拔” 的节点（从原链表头部1开始）
plaintext
原链表：1 → 2 → 3 → null
newHead：null
curr：1（指向原链表的第一个节点）
第一步：插入节点 1
-
先记下原链表的下一个节点（防止 “拔” 走
1后找不到2）：
ListNode next = curr.next;（next现在指向2） -
把当前节点
1插到新链表头部：
curr.next = newHead;（1的next指向新链表头部null→1 → null） -
更新新链表的头部：
newHead = curr;（新链表头部现在是1） -
处理下一个节点：
curr = next;（curr移到2，准备处理下一个节点）
此时状态：
plaintext
原链表剩余：2 → 3 → null
newHead：1 → null
curr：2
第二步：插入节点 2
-
记下原链表的下一个节点：
ListNode next = curr.next;（next指向3） -
把
2插到新链表头部：
curr.next = newHead;（2的next指向新链表头部1→2 → 1 → null） -
更新新链表的头部：
newHead = curr;（新链表头部现在是2） -
处理下一个节点：
curr = next;（curr移到3）
此时状态：
plaintext
原链表剩余：3 → null
newHead：2 → 1 → null
curr：3
第三步：插入节点 3
-
记下原链表的下一个节点：
ListNode next = curr.next;（next指向null） -
把
3插到新链表头部：
curr.next = newHead;（3的next指向新链表头部2→3 → 2 → 1 → null） -
更新新链表的头部：
newHead = curr;（新链表头部现在是3） -
处理下一个节点：
curr = next;（curr移到null）
此时状态：
plaintext
原链表剩余：null
newHead：3 → 2 → 1 → null
curr：null
结束，返回新链表头部
当 curr 为 null 时，所有节点都已插入新链表，newHead 就是反转后的头节点，返回 newHead 即可。
插头法代码实现
java
class Solution {public ListNode reverseList(ListNode head) {ListNode newHead = null; // 新链表的头部（初始为空）ListNode curr = head; // 当前要处理的节点（从原链表头开始）while (curr != null) {ListNode next = curr.next; // 1. 记下原链表的下一个节点curr.next = newHead; // 2. 把当前节点插到新链表头部newHead = curr; // 3. 更新新链表头部为当前节点curr = next; // 4. 处理下一个节点}return newHead; // 新链表头部就是反转后的结果}
}
插头法 vs 官方双指针法
本质上，这两种方法是同一种思路的不同表述：
- 官方双指针法中，
prev其实就是 “新链表的头部”（newHead），curr是 “当前要处理的节点”。 - 两者都是通过逐个反转节点指针实现反转，时间复杂度都是 O (n)，空间复杂度都是 O (1)。
区别在于：
- 双指针法更强调 “指针反向移动” 的过程。
- 插头法更形象，把 “反转” 理解为 “重新构建一个新链表，每次往头部插节点”。
为什么叫 “插头法”？
因为每次处理节点时，都像在新链表的 “头部” 插了一个插头，新节点永远在最前面，自然就形成了反转的效果。这个名字非常形象，记住 “插头” 就记住了核心操作：每次把节点往新链表的头上插。
多画几遍步骤，你会发现这种方法比想象中简单！ 😊
我感觉就是拔下来反序插好。
你这个总结太到位了！“拔下来，反序插好” 这 7 个字，精准抓住了反转链表的核心逻辑 —— 不管是双指针法还是插头法，本质都是这么回事！
咱们再用 “拔插” 的思路拆解一下，更有画面感：
- 原链表就像一串珠子：1→2→3→null（珠子按顺序串在一根线上，线就是
next指针）。 - “拔” 的动作：从第一个珠子（1）开始，一个个从原线上拆下来（用
next暂时记住下一个要拆的珠子，防止线断了找不着）。 - “反序插” 的动作：拆下来的珠子不按原来的顺序串，而是每次都把新拆的珠子怼到最前面（比如拆 2 时，让 2 的线连 1；拆 3 时，让 3 的线连 2）。
- 最后串成新珠子串：3→2→1→null（原来的尾巴变成了头，完美反转）。
这种 “拆一个、插一个到新头部” 的过程，既避免了额外用数组存节点（省空间），又能一次遍历完成（省时间），确实是最巧妙的思路。
记住你这个 “拔插” 口诀，以后不管遇到单链表反转、部分反转，甚至环形链表相关的问题，都能快速联想到核心操作 —— 本质都是通过调整 “线”（next指针）的连接顺序，实现节点的重新排列。