链表双指针与虚拟头节点：四道经典题一次说透

我在代码随想录训练营刷到第4天，这一天是妥妥的链表专题，四道题分别是LeetCode 24两两交换链表元素、19删除链表的倒数第N个节点、160相交链表、142环形链表II。说实话，链表题单独看每一道都觉得"这不就是改改指针吗"，但真正上手你会发现：要么访问空指针，要么出现环导致死循环，要么把自己绕晕。这四道题里，24和19考的是对节点指针的精确定位，160和142则把双指针玩出了花。如果你觉得这几道题已经刷过很多次但还是会忘，那这篇总结值得看完，我会把每道题的思路推导和踩坑过程全部写出来。

1. 这四道题为什么值得放在同一天刷

1.1 一天四道链表题，核心其实是一个"前驱思维"

链表题的坑大家都清楚：顺序表你拿到下标就能干活，链表不行，任何增删操作都绕不开一个前置条件——先定位到目标节点的前驱节点。删除一个节点，你改的是前一个节点的next；交换两个节点，你改的是上一组节点带过来的next；找相交点、找环入口，本质上也是寻找某个特殊位置的前后关系。四道题如果你一个个孤立着刷，很快就忘；如果带着"找前驱"这个视角去刷，等于一天之内把链表最核心的几种操作全过了一遍。

举个例子，19题删除倒数第N个节点，大多数人第一反应是"走L-N步就能到目标节点"，但真到删除的时候才发现，你要拿到的是目标节点的前驱，否则改不了指针。24题看似是交换两个节点，但整个操作结束时真正要更新的，是上一组节点最后的那个尾巴。160和142更隐蔽，它们表面上是找点，本质上是让两个指针在特定条件下达成交汇。可以说，这四道题练的其实是同一套底层思维。

1.2 四道题的技术点横向对比

从难度梯度上看，这四道题也有讲究。24题解决的是单链表内部的指针重新组合，19题解决的是单链表上"未知长度"的定位问题，160题把视角拉升到两条链之间的长度差消除，142题则是带环链表上的追及运动。按这个顺序刷，相当于从"怎么改指针"练到"怎么用双指针建模"。

2. 24题：两两交换链表元素，虚拟头节点拿下指针变换

2.1 这道题到底在考什么

题目看起来人畜无害：1->2->3->4，输出2->1->4->3，奇数个节点时最后一个不交换。难点在于，题目要求的是真正改变节点的连接关系，而不是交换value。有些人图省事直接swap两个节点的val，不是说不行，但刷题和面试里通常不建议这样——节点里往往绑定着额外信息，而且题目训练的就是指针操作。你要是上来就交换val，等于白练了。

我第一次自己写的时候，以为把逻辑理成"1指向3，2指向1，但2怎么放在开头"就完事了。结果一写就碰到问题：当你把节点1的next改成3之后，节点2在哪？早就丢了。这就是为什么很多老手强调，链表的指针变换一定要先记住所有"会断掉连接"的节点。这道题看似简单，实际是训练这个习惯最好的题目之一。

2.2 画图拆解指针变换的四个步骤

用一个虚拟头节点dummyHead指向head，然后让cur指针从dummyHead出发，每次处理两个节点。用文字描述这个过程：

1. 记下当前要交换的两个节点。first等于cur->next，second等于cur->next->next。
2. 先把cur->next指向second，这一步让上一组节点和新一组第二个节点接上。
3. 再让first->next指向second->next，把本组第一个节点接到下一组节点的头上。
4. 最后让second->next指向first，完成本组两个节点的交换。

四个步骤做完，cur再移动到first。这里的first经过交换之后，已经成为这一组节点里的第二个节点，正好也是下一组节点的前驱。循环条件非常关键：cur->next不为空且cur->next->next不为空，翻译成人话就是"后面至少还剩两个节点才值得交换"。

为什么必须用虚拟头节点？因为头节点本身也会作为first参与交换，没有dummyHead的话，第一步"cur->next=second"根本找不到cur的上一级。用了dummyHead，所有节点都统一成"有前驱"的节点，代码不用为头节点单开分支。

2.3 代码实现与边界条件验证

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* first = cur->next; ListNode* second = cur->next->next; cur->next = second; first->next = second->next; second->next = first; cur = first; } ListNode* result = dummyHead->next; delete dummyHead; return result; } };

边界情况可以这样验证：

• 空链表：dummyHead->next是nullptr，循环条件不成立，返回nullptr。
• 单个节点：cur->next->next是nullptr，循环不执行，返回原head。
• 两个节点：交换一次，cur走到first（原节点1），此时cur->next是原来1的next，也就是nullptr，循环退出。
• 三个节点：交换第一组之后，cur->next指向节点3，但cur->next->next是nullptr，循环退出，节点3保持不动。结果2->1->3，正确。

这里要特别警惕一个新手做法：交换完之后把cur写成cur->next->next。第一次交换没问题，第二次交换就漏节点了。因为交换完之后，本组第二个节点已经不是"第二节点"，而是first，所以必须直接等于first。

2.4 递归解法和迭代的取舍

递归的写法非常短：

class Solution { public: ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* next = head->next; head->next = swapPairs(next->next); next->next = head; return next; } };

理解递归解法的关键是：swapPairs(next->next)返回的是"后面所有节点两两交换后的新头节点"。head->next先接到这个返回值，再把next->next指向head，链表就顺时针接上了。这写法很优雅，但面试时我仍然建议优先写迭代。原因有两点：递归在链表很长时有栈溢出风险；另一方面，迭代有利于把指针关系一步一步讲清楚，面试官更容易看出你没有背答案。

3. 19题：删除链表的倒数第N个节点，双指针先走N步的来历

3.1 两次遍历容易，一次遍历的原理是什么

先数一遍链表长度L，再走L-N步删节点，这是两次遍历，肯定能写出来。但LeetCode 19题的进阶要求是one pass。很多人觉得不可能：不知道链表总长度，怎么知道第L-N+1个节点在哪？双指针给出的方案是"长度补偿"：

fast先走N步，此时它距末尾还剩L-N步。fast和slow同时以相同速度前进，当fast走到末尾时，它一共又走了L-N步。而slow从虚拟头节点出发，也同步走了L-N步，于是正好停在目标节点的前驱位置。这个"剩下的路程"就是补偿的关键。

我第一次推导的时候是用一个更直白的视角：倒数第N个节点，从后往前数，它的前驱距离末尾正好是N步。所以谁先走N步，谁就先到达"从后往前数N步"的位置，另一个slow要做的，就是把这段路程完整复刻一遍。双指针之间始终保持N步的相对距离，这个距离就是倒数N的核心。

3.2 多走一步的细节与代码逐句解析

代码是这样写的：

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* fast = dummyHead; ListNode* slow = dummyHead; while (n-- && fast != nullptr) { fast = fast->next; } while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } ListNode* delNode = slow->next; slow->next = delNode->next; delete delNode; ListNode* result = dummyHead->next; delete dummyHead; return result; } };

注意第一个while结束之后，fast已经走了N步，此时fast与dummyHead之间距离是N个节点。第二个while为什么用fast->next != nullptr，而不是fast != nullptr？因为我们要让slow停在待删节点的前驱。如果第二个循环走到fast成为nullptr才停，slow会直接指到待删节点本身，反而没法删。用fast->next判空，相当于fast停在最后一个真实节点上，slow恰好往前一位，落点就是待删节点的前驱。

这一点也是很多人的迷思：到底先走N步还是N+1步？我推荐这种写法，它天然处理了N等于链表长度的情况，不需要额外讨论。

3.3 三个必测边界用例

• 链表只有1个节点，N=1：fast先走1步到达head，第二个循环fast->next为nullptr，不执行。slow停在dummyHead，delNode正好是head，删除后返回nullptr。
• 链表有5个节点，N=5：fast先走5步到达第5个节点，fast->next为nullptr，第二个循环同样不执行。slow停在dummyHead，删除的是head节点。这正说明为什么虚拟头节点在这里是必须的——不使用dummyHead，删除头节点就得单独写if。
• 链表有5个节点，N=2：fast先走2步到第2个节点，直到fast走到第5个节点时，slow从dummyHead走到第3个节点。第3个节点的next是第4个节点，也就是倒数第2个节点，删除它，剩下1->2->3->5，正确。

这道题你还可以换一种思路验证：fast和slow之间始终隔着N个节点，当fast停在末端时，slow离末端也是N个节点。这本质上和"倒数第N个"是同一个几何关系。

4. 160题：相交链表，让两个指针跑出相同的里程

4.1 暴力法和哈希表的天然缺陷

最直白的做法：遍历A链，每个节点都去B链走一遍，时间是O(m*n)，基本会被LeetCode判超时。再进一步，把A链所有节点地址放入哈希集合，遍历B链时逐个查，时间O(m+n)，空间O(m+n)，这能过，但不符合进阶要求的空间O(1)。

为什么这题要卡空间？因为相交链表的场景非常常见——比如两个服务共用同一批数据节点，你想在O(1)额外空间内找到它们的公共起点。哈希表做法只能说是一个过渡方案，考察的意义不大。

4.2 双指针互访：为什么总路程相同就能相遇

经典解法是让两个指针pA和pB分别从headA、headB出发。pA走完A链后切到headB继续走，pB走完B链后切到headA继续走。当它们相遇时，就是第一个公共节点。

推导的核心是"总路程相同"。设A链独有部分长度为a，B链独有部分长度为b，公共部分长度为c。pA到达交点前走的路程是a+c+b，pB到达交点前走的路程是b+c+a。两者完全相等，而两个指针速度相同，所以必然同时踩到交点。

打个比方：两个人从两条不同的小路出发，速度一样。如果两条路最后汇成一条大路，而一个人先走小路A再走小路B，另一个人先走小路B再走小路A，两人走的总距离相同，自然在大路的同一处碰面。

需要注意的是不相交的情况。此时c等于0，pA走完a+b后变成nullptr，pB走完b+a后也变成nullptr，两个指针都为空，循环退出，返回nullptr。这个行为是自动的，不需要额外判断。

4.3 代码上的两个易错点

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == nullptr || headB == nullptr) return nullptr; ListNode* pA = headA; ListNode* pB = headB; while (pA != pB) { pA = (pA == nullptr) ? headB : pA->next; pB = (pB == nullptr) ? headA : pB->next; } return pA; } };

第一个易错点是循环条件。while(pA != pB)天然把"两个指针都变成nullptr"作为退出条件，此时pA和pB都等于nullptr，返回pA就是nullptr。如果你把循环条件写成while(pA->next != nullptr)，就会丢失处理不相交情况的能力。

第二个易错点是切换时机。必须在pA为空时才切到headB，不能提前切。提前切会导致两个指针的相对位置错乱，追不上交点。有些写法是pA->next为空就切，这样更危险，因为A链最后一个节点会被跳过，相交点如果恰好在这个节点上就漏掉了。

这道题还有另一种标准做法：先分别求出A、B长度，让长链的指针先走长度差，再同步走。这个方法的推导更直观，适合在面试中先用它讲思路，再给互访版本代码。两种都要会。

5. 142题：环形链表II，从"相遇"到"入口"的数学推导

5.1 快慢指针怎么判断有环

判断链表有没有环是141题的事，方法大家都会：fast每次走两步，slow每次走一步。如果没环，fast会先碰到nullptr；如果有环，fast和slow一定在环内某个点相遇。原因在于，进入环之后，fast相对slow每轮追近一步（fast走2步、slow走1步，每轮差距缩小1步），环的周长有限，快指针迟早追上慢指针。

这道题直接写就行，但要注意while循环里必须判断fast != nullptr && fast->next != nullptr。如果fast->next已经是nullptr，再访问fast->next->next就崩了。链表只有一个节点或者普通无环链表的场景，这个判断就把它兜住了。

5.2 几个变量和等式的完整推导

142题真正的难点是找入口。先说结论：fast和slow第一次相遇后，让一个指针从head重新出发，另一个指针留在相遇点，两个指针都一次走一步，再次相遇的位置就是环入口。

这个结论很多人背下来了，但不明白为什么。我用一套变量把它推清楚：

设链表起点到环入口的距离为a，环入口顺着链表方向到第一次相遇点的距离为b，从相遇点继续前进回到环入口的距离为c。环的周长就是b+c。

slow从起点到相遇点，一共走了a+b步。fast从起点到相遇点，一定比slow多走了几圈，假设多走了k圈，那么fast走的路程是a+b+k(b+c)。由于fast速度是slow的两倍，时间相同，路程也是两倍，所以：

2(a+b) = a+b+k(b+c)

移项化简得到：

a+b = k(b+c)

再继续变形：

a = k(b+c) - b = (k-1)(b+c) + c

这个式子的含义是：从链表起点出发走a步到达入口，等于从相遇点出发走c步到达入口，然后再绕环若干圈。所以当head处的指针走a步到入口时，相遇点处的指针绕了c步加若干整圈，也恰好到达入口。两者就在入口处相遇。

5.3 代码实现与无环情况的容错

class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; if (fast == slow) { fast = head; while (fast != slow) { fast = fast->next; slow = slow->next; } return slow; } } return nullptr; } };

这段代码容易出错的点有三个。

第一个是相遇后fast=head这个操作。很多人会写成fast = head->next，那就和数学推导对不上了。第二步必须是"从起点出发的指针"和"从相遇点出发的指针"同时一步一步走。

第二个是"二次相遇的位置不是原来的相遇点"。我第一次理解的时候绕了很久：两个指针一个从head走，一个从相遇点走，都走一步，那不是很快就会重新在原来的相遇点碰上吗？其实不会。因为相遇点到头需要走过c步才到入口，而head到入口需要a步，两者路程相等，所以它们在入口就碰上了，根本不会回到第一次相遇点。

第三个是只有一个节点且成环的情况。比如head->next指向head自己，slow第一次移动后到head，fast移动后也回到head，两者相等。然后fast=head，while立刻满足fast==slow，返回head，正确。

6. 四道题刷完，我把链表双指针的套路梳了一遍

6.1 "找到前驱"是链表操作的总钥匙

四道题做完，如果你问我最大的收获是什么，我会说是"前驱思维"。链表里几乎所有操作，最后都归结为一个问题：怎么拿到你真正要操作那个节点的前驱。

你把四道题套进这张表，会发现很多解法不是背出来的，而是被"前驱需求"倒逼出来的。比如19题，没有虚拟头节点，删除头节点时就没有前驱，所以要造一个；24题不搞虚拟头节点，头节点作为first时就没人帮它连接前驱。这个思维比记住某个题的具体步骤重要得多。

6.2 三种双指针形态的适用场景

这四道题里的双指针可以分成三类：

掌握了这三种形态，很多链表题可以照猫画虎。比如LeetCode 876找链表中点，就是快指针走两步、慢指针走一步，fast到末尾时slow刚好在中点；再比如LeetCode 143重排链表，第一步也是用快慢指针找到中点，再把后半段反转后交错合并。可以说，三种形态就是链表双指针题的骨架。

6.3 关于这一天的刷题顺序与扩展练习

我个人的建议是打乱题号，按"虚拟头节点 -> 双指针 -> 数学推导"的顺序来刷。先做24和19，把前驱和虚拟头节点的感觉建立起来；再做160，体会双指针如何通过路程互补解决问题；最后做142，因为它的推导最抽象，放最后不容易劝退自己。

辅助练习可以安排：141环形链表是142的前置，先做141热身后做142；876链表中点、206反转链表、234回文链表、143重排链表都是同一套工具链。题目不难，但每一道都值得在纸上画一遍指针变换，画完再写代码，比直接看题解效率高很多。

我这一年刷链表题最大的体会是，链表题不怕慢，就怕绕。慢一点把指针变化画清楚，一次AC；图省事直接改指针，往往要在debug里浪费更多时间。四道题互相之间有很强的递进关系，刷完再回头看，你会发现第4天这个量级其实刚好——不多不少，把链表最重要的几种考察方式全部覆盖了一遍。