力扣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.nextpre;也就是1.nextnull;如果直接这样做链表会变成1 - null 2 - 3 - null问题在于节点1原来通向节点2的指针被覆盖了而我们还没有保存节点2。于是从1出发后面的2 - 3就无法再访问相当于丢失了未处理的链表。所以修改cur.next之前必须先保存原来的下一个节点ListNodenextcur.next;这是本题最关键的一步。2. 三个指针分别表示什么我们使用三个指针ListNodeprenull;ListNodecurhead;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准备处理下一个节点代码就是ListNodenextcur.next;cur.nextpre;precur;curnext;可以把它记成一句话保存后继 - 反转指向 - 指针前进其中第一步必须排在第二步之前因为一旦执行cur.next precur原来的后继关系就被覆盖了。4. 用1 - 2 - 3完整推演初始状态null 1 - 2 - 3 - null pre cur第 1 轮处理节点 1第一步保存节点1原本的下一个节点nextcur.next;next 2第二步反转节点1的指向cur.nextpre;null - 1 2 - 3 - null cur第三步移动两个主指针precur;curnext;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。ListNodeprenull;// cur 指向当前需要处理、需要反转的节点。ListNodecurhead;// 当 cur 不为 null说明还有节点未处理。while(cur!null){// 先保存 cur 原本的下一个节点。// 下一步会覆盖 cur.next不提前保存后续链表会丢失。ListNodenextcur.next;// 让当前节点指向已经反转部分的头节点// 从而完成当前节点的指针反转。cur.nextpre;// 当前节点已经成为反转完成部分的新头节点。precur;// 继续处理原链表中的下一个节点。curnext;}// 所有节点都处理完后pre 就是反转后链表的新头节点。returnpre;}}6. 为什么返回pre而不是head原来的head指向节点1head | v 1 - 2 - 3 - null反转之后节点1会变成尾节点3 - 2 - 1 - null ^ head所以原来的head不再能代表新链表的头节点。而在每一轮循环中precur;都会让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 一起前进。