力扣hot100-206.反转链表-双指针详解

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之前必须先保存原来的下一个节点：

ListNodenext=cur.next;

这是本题最关键的一步。

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

我们使用三个指针：

ListNodepre=null;ListNodecur=head;ListNodenext;

它们的职责是：

刚开始时：

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，准备处理下一个节点

代码就是：

ListNodenext=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 代码完整注释

classSolution{publicListNodereverseList(ListNodehead){// pre 指向已经完成反转部分的头节点。// 开始时还没有节点被反转，因此为 null。ListNodepre=null;// cur 指向当前需要处理、需要反转的节点。ListNodecur=head;// 当 cur 不为 null，说明还有节点未处理。while(cur!=null){// 先保存 cur 原本的下一个节点。// 下一步会覆盖 cur.next；不提前保存，后续链表会丢失。ListNodenext=cur.next;// 让当前节点指向已经反转部分的头节点，// 从而完成当前节点的指针反转。cur.next=pre;// 当前节点已经成为反转完成部分的新头节点。pre=cur;// 继续处理原链表中的下一个节点。cur=next;}// 所有节点都处理完后，pre 就是反转后链表的新头节点。returnpre;}}

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 一起前进。