力扣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 | 已经反转完成部分的头节点 |
cur | 当前正在处理、准备反转的节点 |
next | 暂存cur原本的下一个节点，防止后续链表丢失 |
刚开始时：
pre = null cur = 1对应的链表状态是：
已反转部分：null 未处理部分：1 -> 2 -> 3 -> 4 -> 5 -> null curpre的含义不是“前一个节点”这么简单。更准确地说：
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 -> null5. 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 一起前进。