链表算法面试四题精讲：虚拟头节点、双指针与快慢指针实战

最近把训练营第四天的链表专题补完了，1月31日的卡拖到今天才填上。题目是24. 两两交换链表中的节点、19. 删除链表的倒数第N个结点、面试题02.07. 链表相交、142. 环形链表||。这四道题放在一起特别有讲究，覆盖了链表操作里最核心的几个技巧：虚拟头节点、双指针、快慢指针，以及一个需要数学推导才能彻底理解的环入口问题。我不是第一次接触这些题，但这次系统性地把四道题连起来做，很多以前靠“背下来”的写法，突然就通了。这篇文章把每道题的思考过程、代码实现和踩坑记录都写出来，尤其会重点解释那些“为什么这么写”的细节——比如为什么要用虚拟头节点、快指针为什么要先走n+1步、环入口那个 a = c 的结论到底怎么来的。准备面试、刷题卡在链表这块的朋友，可以跟着走一遍，应该能省不少时间。

1. 链表专题的整体思路：四道题背后的考点布局

1.1 为什么链表题值得单独花一天刷

链表在算法面试里的出现频率极高，但奇怪的是，它不像数组题那样有那么多“花活”，考点相对固定，套路也比较有限。可就是这么几个套路，很多人在面试时还是会写错。核心原因在于链表和数组的思维模式完全不同——数组是连续内存，访问靠下标，写起来直觉化；链表是离散内存，访问靠指针的 next 关系，脑子里必须时刻有一张“节点关系图”，否则很容易在指针操作中丢失节点，或者访问到空指针。

这四道题恰好把链表题里最高频的思维模型都覆盖了：两两交换考察“在链表中改变两个节点关系时，必须通过前驱节点来操作”；删除倒数第N个节点考察“用双指针一次遍历完成定位”；链表相交考察“如何用长度差把两个起点对齐”；环形链表则考察“快慢指针检测环，以及通过数学推导找到环入口”。把这四道题吃透，链表题的大部分变体都能找到对应的思路落脚点。

1.2 四道题的共性技巧与刷题顺序

我先用一张表把这四道题的关键信息整理出来，方便对照着看：

从刷题顺序上看，这四道题也有明显的递进关系：先会改变节点的链接关系（24题），再学精确定位并删除（19题），然后是判断两个链表的关系（02.07题），最后上升到带环链表的结构分析（142题）。难度逐级增加，技巧也从“操作手熟”走向“思路推导”。练完这四道题，我对链表题的信心提升了不少，后续再做反转链表、合并链表、排序链表这些题，也会觉得底层逻辑是相通的。

2. 前两道真题：虚拟头节点与双指针的正确打开方式

2.1 两两交换链表中的节点：不要在修改指针时“丢节点”

先看题目的具体要求：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。题目强调不能只改节点内部的值，必须真正交换节点。这个强调很重要，因为如果只交换值，题目就退化成简单的数组元素交换了，完全失去了链表操作的意义。

我的第一反应是引入一个虚拟头节点（dummy head），好处在于：头节点没有前驱节点，如果直接从头节点开始交换，需要单独处理头节点的情况。有了虚拟头节点，整个链表的所有节点都变得“有前驱”，操作逻辑统一了，不需要在代码里写 if 判断特殊分支，也不容易遗漏头节点的更新。

交换的逻辑看着不复杂：当前指针 cur 指向待交换节点的前驱，cur->next 是第一个节点 first，cur->next->next 是第二个节点 second，再往后是下一对待交换节点的开头 third。交换的目标是让 cur->next 指向 second，second->next 指向 first，first->next 指向 third。但这里有个极其容易出错的点：一旦你修改了 first 的 next 或者 second 的 next，原链表的部分连接关系就断了，如果不提前保存某个节点的指针，后面就再也找不到那个节点了。

我通常的做法是把 first 和 third 先存到临时变量里，再执行修改操作。参考代码如下：

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* third = cur->next->next->next; // 第三个节点，提前保存 cur->next = cur->next->next; // 步骤1：cur 指向第二个节点 cur->next->next = first; // 步骤2：让第二个节点指向第一个节点 first->next = third; // 步骤3：让第一个节点指向第三个节点 cur = cur->next->next; // cur 移动到下一对待交换节点的前驱 } return dummyHead->next; }

步骤顺序很关键，尤其步骤3里first->next = third这一步，如果换到步骤1之前执行，会导致 chain 断掉，因为 first 一旦指向 third，原来 first 到 second 的连接就没了，后面的 second 节点就找不到了。

再解释一下循环终止条件为什么是cur->next != nullptr && cur->next->next != nullptr：只有下一个和下下个节点都存在，才有得换。如果剩余节点数量不足两个，就不需要交换了。这里特别容易打成while (cur->next != nullptr)然后因为空指针问题报错，每次写完我都会下意识检查一遍这个条件。

另外有个小细节：返回值一定是dummyHead->next，不能返回 head。因为两两交换后，head 可能不再是新链表的头节点了。比如链表是 1->2->3->4，交换后变成 2->1->4->3，新头部是 2 不是原来的 1。用dummyHead->next统一返回，就不会出错。

2.2 删除链表的倒数第N个结点：为什么快指针要先走n+1步

删除倒数第N个节点的常规思路是先遍历一遍得到链表长度，再走长度减N步到达目标节点的前一个位置。这种做法没问题，但需要遍历两次链表。进阶要求是只遍历一次，这就需要双指针登场了。

思路很巧妙：让 fast 指针先走 n+1 步，然后 slow 指针和 fast 指针同时以相同速度移动。当 fast 走到链表末尾的空指针时，slow 正好停在待删除节点的前一个节点。为什么是 n+1 而不是 n？因为如果 fast 走 n 步，两个指针同时出发后，当 fast 到末尾时，slow 指向的是倒数第 n 个节点，也就是要删除的目标节点。可删除操作需要修改的是“目标节点的前驱节点”的 next 指针，所以我们必须让 slow 停在目标节点的前驱上，因此 fast 要提前多走一步。

参考实现：

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* fast = dummyHead; ListNode* slow = dummyHead; // 让 fast 先走 n+1 步 for (int i = 0; i <= n; i++) { fast = fast->next; } // fast 和 slow 同步移动，直到 fast 到达链表末尾 while (fast != nullptr) { fast = fast->next; slow = slow->next; } // slow 的下一个节点就是倒数第 n 个节点，执行删除 slow->next = slow->next->next; return dummyHead->next; }

边界情况也必须想一想：如果 n 等于链表长度，那么要删除的是头节点。这时 fast 先走 n+1 步后会变成空指针，但因为有了虚拟头节点，slow 仍然可以从虚拟头节点开始移动，最终让 slow 的 next 指向原来的第二个节点，等于把头节点删掉了。这个过程完全不需要特判，虚拟头节点帮我们兜住了一个看似会越界的场景。

我早期踩过一个坑：题目给的是“倒数第N个结点”，我直接在第一遍遍历时用栈存节点，然后出栈找第N个。这种思路也能做，但空间复杂度是O(n)，而且代码啰嗦。双指针做法的空间复杂度是O(1)，代码也简洁，面试的时候优先讲这种方案，面试官听了会点头。

3. 后两道进阶题：长度差消除与环入口的数学推导

3.1 链表相交：先对齐起点再一起走

面试题02.07的要求是：给定两个单链表，找出它们相交的起始节点，如果无交点则返回 null。注意这里的相交不是值相等，而是指针指向同一个节点。

先说一个不太推荐的暴力思路：固定一个链表的每个节点，去另一个链表里逐个比较，时间复杂度O(m*n)，面试时基本不会采用。更好的做法是用“长度差”来消除两个链表起点不同的问题。

道理很简单：相交之后的链表部分是完全重合的，也就是说，相交之后两个链表从某个节点开始，后面的每一步都走同样的节点。既然相交部分相同，两个链表长度差一定只体现在相交之前的节点上。做法是先把两个链表的长度算出来，让长的链表指针先走差值步，然后两个指针再同时走，不停判断是否指向同一个节点，如果相等就直接返回该节点，如果走完了都不相等，说明没有交点。

参考代码：

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { if (headA == nullptr || headB == nullptr) return nullptr; int lenA = 0, lenB = 0; ListNode* curA = headA; ListNode* curB = headB; while (curA != nullptr) { lenA++; curA = curA->next; } while (curB != nullptr) { lenB++; curB = curB->next; } curA = headA; curB = headB; // 让 curA 指向较长链表的头节点 if (lenA < lenB) { swap(lenA, lenB); swap(curA, curB); } int gap = lenA - lenB; while (gap--) { curA = curA->next; } while (curA != nullptr) { if (curA == curB) return curA; curA = curA->next; curB = curB->next; } return nullptr; }

这段代码里我用swap统一了“谁长谁先走”的逻辑，避免了写两遍几乎相同的 while 循环。这种做法在题目讨论区里很常见，也推荐大家养成习惯——能用一次交换减少代码重复，就不要写对称的 if-else。

做这道题的时候我还想过另一个解法：把两个链表首尾相接，比如 A 链表的末尾接上 B 链表的头，B 链表的末尾接上 A 链表的头。两个指针一起走，最终会同时到达交点或者同时到达空指针。这种实现很巧妙，代码甚至更短，但对初学者来说，理解起来没有长度差方案直观。面试的时候，我倾向于先说长度差方案，因为思路容易讲清楚，推导也不容易卡住；等对方继续追问“还有没有别的做法”时，再补充拼接方案，反而能体现思维的广度。

3.2 环形链表II：为什么相遇后从头节点出发就一定能找到入口

142题是这四道题里最需要动脑子的一题。前两段都只是局部调整指针指向，这道题则需要通过数学关系定位环的起点。

先回顾一下经典检测环的方法：慢指针 slow 每次走一步，快指针 fast 每次走两步，从同一个起点出发。如果链表中有环，两个指针最终一定会在环中的某个点相遇；如果没环，fast 会先到达空指针。

这道题的难点在于后面：找到相遇点之后，如何确定环的入口？

教材式的做法是：相遇时，把一个指针（设为 index1）指向链表头节点，另一个指针（设为 index2）保持在相遇点。然后两个指针每次都走一步，它们再次相遇的地方就是环入口。这个结论看起来很神奇，很多人第一次看会直接背下来，但如果不理解背后的推导，面试时很容易被追问得卡壳。

我来完整地推一遍。设链表的头节点到环入口的距离为 a，环入口到 fast 和 slow 相遇点的距离为 b，相遇点继续沿着环走到环入口的距离为 c。环的一整圈长度就是 b + c。

当 slow 和 fast 相遇时：

• slow 走了 a + b 步。
• fast 走了 a + b + (b + c) 步，因为 fast 在相遇前比 slow 多走了一圈还多？等等，这里要更严谨一些。fast 的速度是 slow 的两倍，所以 fast 的步数是 slow 的两倍。fast 总共走了 a + b + k*(b+c)，其中 k 是 fast 已经整圈绕行的次数。根据速度关系：

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

化简得：

a + b = k * (b + c)

如果取 k=1（最少的情况，也就是 fast 在环里绕了一整圈之后追上 slow），那么：

a + b = b + c

解得 a = c。

这个 a = c 意味着什么？从头节点走到环入口的距离，等于从相遇点继续走到环入口的距离。所以如果两个指针分别从头节点和相遇点出发，每次走一步，它们会在环入口相遇。这就是结论的完整来源。

我补充一下为什么可以默认 k=1：slow 刚进入环时，fast 已经在环内了。由于 fast 的速度是 slow 的两倍，它的相对速度是1（相当于 slow 不动，fast 每步靠近一个节点的距离）。而 fast 与 slow 的距离最多小于一整圈环长，所以 fast 在 slow 走完第一圈环之前就能追上它，此时 k 就等于1。不需要讨论更复杂的情况。

理清这个推导之后，再看代码就非常清晰了：

ListNode* detectCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 有环，开始找环入口 ListNode* index1 = head; ListNode* index2 = fast; while (index1 != index2) { index1 = index1->next; index2 = index2->next; } return index1; } } return nullptr; // 没有环 }

写代码时最容易犯的错误是在快慢指针移动后没判空就继续访问fast->next->next，如果 fast 恰好是空指针就会直接崩溃。所以 while 循环条件必须先写fast != nullptr && fast->next != nullptr，保证 fast 和 fast 的下一个节点都非空，才能继续走两步。这个条件如果只写while (fast != nullptr)，循环里面第二次访问fast->next->next仍然可能触发空指针异常，跑测试用例时就容易出现 Segfault。

还有个小细节：相遇时 fast 指针是不允许回退的，直接把它当前的位置作为 index2 的起点就行。这个位置就是推导中的相遇点，从它开始走 c 步到环入口。

4. 实操踩坑记录与问题排查技巧

4.1 指针操作顺序：每次修改 next 前先问“谁还指向它”

链表题几乎所有的运行时错误都指向同一个原因：在某个节点成为“孤节点”之后，才想起来要读取它。两两交换那道题，第一次写的时候我把顺序写成了：先让 first->next 指向 third，再让 cur->next 指向 second。结果运行时报错，链表输出变成了 2->2->4...这种奇怪的结果。稍微画一下图就明白了：当我修改 first->next 之后，原链表中 first 指向 second 的连接已经断开，此时如果后续步骤需要读取 second，很难通过指针关系从 first 或 cur 找到它。正确做法是先把需要保留的节点存入临时变量，再进行指针修改，就像我在代码中保存third那样。

这里有一个可以贯穿所有链表操作的原则：如果你要修改某个节点的 next 指向，先确认这个节点的旧 next 所指向的节点是否还需要被访问，如果还需要，先把这个旧 next 存到临时变量里。宁可多写一行临时变量，也不能让某个节点凭空“消失”。

4.2 环形链表的死循环问题：不要盲测，先加计数器

142题如果在 fast 和 slow 的移动代码里少写了一个fast->next->next而是写成了fast->next，会直接造成死循环：fast 和 slow 速度一样，永远不可能相遇，程序会一直跑到超时。我第二次刷的时候是直接在本地编译器里跑测试用例，结果程序没反应，控制台卡住。赶紧在 while 循环里加了一个计数变量，限制最多执行 1000 次，打印出每一步的节点地址，才发现 fast 根本没有进入“两步跳”的节奏。

遇到疑似死循环时，调试方法没有想象中复杂：要么加计数器，要么在循环里打印每次节点访问的地址。不要凭感觉去猜哪一行出错，链表问题的地址输出非常直观，打出来看一眼就知道指针走了什么路径。

4.3 常见问题速查表

我把这四道题练习过程中最容易踩的坑整理成了一张速查表，写完代码之后对着自查，能省不少调试时间：

5. 补打卡复盘与链表题的提升建议

5.1 为什么算法打卡不能长期断档

这次补的是1月31日的卡，断的那几天刚好遇到工作上赶项目，晚上回家确实没有完整的时间坐下来写题。一天断掉其实问题不大，但如果连续断一周，再回头看链表题，你会明显感觉到指针操作的熟练度下降了。算法能力是一个典型的“用进废退”型技能，它的提升依赖于连续的高频刺激。哪怕每天只做一道题，也比隔三天做十道题效果更好。连续刷题能让你在下一次碰到类似题时，迅速在大脑里检索到对应的套路。断档最麻烦的是重新捡起来需要额外花时间热身，实际效率反而更低。训练营里如果有人跟我一样中途断了，不要有心理负担，直接补上就好，重点是之后维持好节奏，别再断。

5.2 从“刷过”到“会讲”：面试表达同样重要

链表题不像是系统设计题，它的代码量通常不大，但面试官很爱在代码写完以后追加问题，比如“为什么要引入虚拟头节点”“这题有没有可能一次遍历完成”“解释一下快慢指针为什么一定会相遇”。如果只会写代码，不清楚背后的设计动机，这种追问很容易露馅。

我的建议是练习的时候尝试用“讲题”的方式过一遍写过的每一道题：先说明题目想考察什么；再讲解决方案的思路，重点讲为什么选这个方案，排除其他方案的理由；然后动手写代码；最后用一两个边界用例走一遍，确认没有漏洞。这四步走完，面试的表达能力会被强行拉高一个台阶。就这四道链表题来说，每道题都值得按这个流程讲一遍。讲熟了以后，你会发现根本不是“背题目”，而是真正理解了链表操作的底层逻辑。

以后再做链表的其他题目时，我会继续沿用这次的思路：虚拟头节点解决边界问题，双指针解决单次遍历的定位问题，快慢指针处理环相关的问题，长链表先对齐再比较。链表专题的精华，差不多就是这四板斧了。