206. 反转链表：双指针详解

题目链接：206. 反转链表

---

算法思路

链表 / 指针操作 / 原地反转

题目给出一条单链表：

1 -> 2 -> 3 -> 4 -> 5 -> null

要求把每个节点的 next 指针方向全部反过来，得到：

5 -> 4 -> 3 -> 2 -> 1 -> null

注意：这里不是创建一条新链表，也不是交换节点中的 val。

真正要做的是：

逐个修改每个节点的 next 指针。

---

1. 为什么不能直接修改 next

假设现在链表是：

1 -> 2 -> 3 -> null

第一次处理节点 1 时，设：

cur = 1
pre = null

反转当前节点，本来需要写：

cur.next = pre;

也就是：

1.next = null;

如果直接这样做，链表会变成：

1 -> null

2 -> 3 -> null

问题在于：节点 1 原来通向节点 2 的指针被覆盖了，而我们还没有保存节点 2。

于是从 1 出发，后面的 2 -> 3 就无法再访问，相当于丢失了未处理的链表。

所以，修改 cur.next 之前必须先保存原来的下一个节点：

ListNode next = cur.next;

这是本题最关键的一步。

---

2. 三个指针分别表示什么

我们使用三个指针：

ListNode pre = null;
ListNode cur = head;
ListNode next;

它们的职责是：

指针	含义
pre	已经反转完成部分的头节点
cur	当前正在处理、准备反转的节点
next	暂存 cur 原本的下一个节点，防止后续链表丢失

刚开始时：

pre = null
cur = 1

对应的链表状态是：

已反转部分：null

未处理部分：1 -> 2 -> 3 -> 4 -> 5 -> null
             cur

pre 的含义不是“前一个节点”这么简单。更准确地说：

pre 始终指向已经反转完成部分的最前面。

因此，所有节点处理完后，pre 就会指向新链表的头节点。

---

3. 每轮循环固定做三件事

处理 cur 时，顺序不能乱：

1. 保存 cur 的原后继节点
2. 修改 cur.next，让它指向 pre
3. 移动 pre 和 cur，准备处理下一个节点

代码就是：

ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;

可以把它记成一句话：

保存后继 -> 反转指向 -> 指针前进

其中第一步必须排在第二步之前；因为一旦执行 cur.next = pre，cur 原来的后继关系就被覆盖了。

---

4. 用 1 -> 2 -> 3 完整推演

初始状态：

null    1 -> 2 -> 3 -> null
pre     cur

第 1 轮：处理节点 1

第一步，保存节点 1 原本的下一个节点：

next = cur.next;

next = 2

第二步，反转节点 1 的指向：

cur.next = pre;

null <- 1    2 -> 3 -> null
       cur

第三步，移动两个主指针：

pre = cur;
cur = next;

null <- 1    2 -> 3 -> null
       pre   cur

节点 1 已经进入“反转完成部分”，节点 2 成为下一轮要处理的节点。

第 2 轮：处理节点 2

先保存后继：

next = 3

再反转当前节点的指向：

null <- 1 <- 2    3 -> null
              cur

移动指针后：

null <- 1 <- 2    3 -> null
              pre  cur

第 3 轮：处理节点 3

先保存后继：

next = null

反转节点 3 的指向：

null <- 1 <- 2 <- 3
                   cur

移动指针：

null <- 1 <- 2 <- 3
                   pre

cur = null

此时没有待处理节点，循环结束。

最终：

pre = 3

所以返回 pre，得到：

3 -> 2 -> 1 -> null

---

5. Java 代码完整注释

class Solution {
    public ListNode reverseList(ListNode head) {
        // pre 指向已经完成反转部分的头节点。
        // 开始时还没有节点被反转，因此为 null。
        ListNode pre = null;

        // cur 指向当前需要处理、需要反转的节点。
        ListNode cur = head;

        // 当 cur 不为 null，说明还有节点未处理。
        while (cur != null) {
            // 先保存 cur 原本的下一个节点。
            // 下一步会覆盖 cur.next；不提前保存，后续链表会丢失。
            ListNode next = cur.next;

            // 让当前节点指向已经反转部分的头节点，
            // 从而完成当前节点的指针反转。
            cur.next = pre;

            // 当前节点已经成为反转完成部分的新头节点。
            pre = cur;

            // 继续处理原链表中的下一个节点。
            cur = next;
        }

        // 所有节点都处理完后，pre 就是反转后链表的新头节点。
        return pre;
    }
}

---

6. 为什么返回 pre，而不是 head

原来的 head 指向节点 1：

head
 |
 v
1 -> 2 -> 3 -> null

反转之后，节点 1 会变成尾节点：

3 -> 2 -> 1 -> null
          ^
        head

所以原来的 head 不再能代表新链表的头节点。

而在每一轮循环中：

pre = cur;

都会让 pre 指向当前已经反转完成部分的最前面。

当所有节点都处理完时：

已反转完成部分 = 整条链表

因此：

pre 就是反转后链表的新头节点。

---

7. 边界情况

空链表：

head = null

此时：

cur = null

循环不会执行，直接返回：

pre = null

结果正确。

只有一个节点：

1 -> null

执行一轮后：

1 -> null

节点仍然是它自己，结果正确。

---

8. 复杂度

假设链表有 n 个节点。

时间复杂度：

O(n)

每个节点只会被 cur 处理一次。

额外空间复杂度：

O(1)

只使用了 pre、cur、next 三个指针变量，没有创建与链表长度相关的额外空间。

一句话记忆：

反转链表时，先用 next 保住后半段，再让 cur 指向 pre，最后让 pre 和 cur 一起前进。