链表算法题通关指南：虚拟头节点与双指针实战-北京尧图网络

说实话Day04 的链表 part02 是代码随想录训练营里第一个真正让我觉得链表题不是背代码而是靠逻辑的节点。前面几天的数组、哈希表还能靠直觉硬刚到了两两交换节点、删除倒数第 N 个节点、链表相交、环形链表这几道题光凭直觉已经不够了必须老老实实画图、抠指针、推数学关系。这篇文章就把我在刷 Day04 时踩过的坑、总结出来的思路、以及最后整理出的通用解题框架全部写出来给同样在跟训练营的朋友一份可以直接照着走的参考。Day04 的题目一共四道24. 两两交换链表中的节点、19. 删除链表的倒数第 N 个节点、面试题 02.07LeetCode 160 同思路链表相交、142. 环形链表 II。如果你没有参加过代码随想录训练营也没关系只要你在准备算法面试、刷 LeetCode 链表专题这四道题就是绕不开的必刷题看完这篇再去写代码手感会完全不一样。先放个整体印象这四道题其实不超过三个核心考点虚拟头节点的使用、双指针的三种玩法快慢指针、相距指针、对齐指针、以及链表操作中指针顺序的掌控。把这三点吃透Day04 就算真正过了。1. 链表题先建立三个底层认知1.1 为什么几乎所有链表操作都要加一个虚拟头节点很多刚刷链表题的人最常问的问题就是为什么要搞一个 dummyHead直接在原链表上操作不是一样吗我一开始也是这么想的直到被删除头节点这个场景折磨到怀疑人生。当你删除的是普通节点时只需要让前一个节点的 next 指向后一个节点就行但删除头节点时根本没有前一个节点只能单独为头节点写 if 分支把 head 往后挪。代码瞬间变得又丑又容易漏。虚拟头节点的作用不是解决某个具体问题而是把头节点这个特例直接抹平。你在 dummyHead 后面接上原链表然后无论操作的是头节点还是中间节点算法逻辑都是同一套不需要任何特殊判断。等于用一个额外的节点换来了代码逻辑的统一性。写代码的时候记住一句话虚拟头节点指向的不是第一个有效节点而是整个链表的前驱。操作和返回的时候真正的头是 dummyHead-next。1.2 链表操作的第一铁律先处理后继再处理前驱链表题写错十有八九是丢节点。举个最典型的例子你要把 cur 的下一个节点指向 next 的下一个节点代码如果写成cur cur-next-next;那完了cur 原来的下一个节点直接丢了后面的链表整体失联。正确做法一定是先保存、再修改ListNode* temp cur-next; // 先记住要处理的节点 cur-next temp-next; // 再断开 / 重连这个习惯的重要性在两两交换节点这道题里会被放到最大。因为那道题要同时操作三个节点指针一动后面一整条链全部要重连不提前保存中间状态画多少图都没用。我的经验是链表题千万别在脑子里演算一定在纸上画出来。每写一步就看一眼我这一步修改了哪个指针被修改前这个指针指向的节点还有没有别的引用如果没有了那这个节点就丢了。这个检查习惯能让你少 debug 半小时。2. 两两交换链表中的节点指针操作的颅内手术2.1 题目到底在让你做什么题目要求把链表的相邻节点两两交换比如 1-2-3-4 变成 2-1-4-3。注意它交换的是节点本身不是节点里的值。这个区别很重要——虽然这题你交换值也能过但面试官要考的就是你操作指针的能力用交换值的方式属于投机取巧完全达不到训练目的。这道题难在哪儿呢难在它不是一个节点的操作而是三个节点的联动前驱节点、第一个待交换节点、第二个待交换节点。而且交换完之后还要保证整个链表的连续性不破。2.2 用虚拟头节点循环拆解三步操作我的做法是定义一个 dummyHeadcur 从 dummyHead 开始每次循环处理 cur 后面的两个节点处理完让 cur 跳到交换后的第二个节点也就是原来的第一个节点继续下一轮。假设当前状态是cur - node1 - node2 - rest...交换过程拆成三步cur 的 next 指向 node2node1 暂时脱离主链但你不能让它跑掉node2 的 next 指向 node1此时 node1 被挂到 node2 后面node1 的 next 指向 rest也就是 node2 原来的 next必须提前存好这个 rest 就是最容易丢的地方。你把 node2-next 改掉之前如果没保存原本的剩余链表那 rest 这一整段就再也找不回来了。所以循环体里第一个动作必须是ListNode* temp cur-next-next-next; // 保存剩余链表然后才是上面三步重连。循环终止条件也要想清楚。因为我们要两两交换所以 cur 后面必须至少有两个节点才能干活。终止条件就是while (cur-next ! nullptr cur-next-next ! nullptr)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* node1 cur-next; ListNode* node2 cur-next-next; ListNode* temp node2-next; cur-next node2; node2-next node1; node1-next temp; cur node1; // cur 跳到下一组的前驱位置 } return dummyHead-next; } };这段代码跑一遍 1-2-3-4第一轮cur 指向 dummyHeadnode11node22temp3。重连后变成 dummyHead-2-1-3-4。cur 跳到 1。第二轮cur 是 1node13node24tempnullptr。重连后变成 2-1-4-3。循环结束。整个过程没有使用任何额外空间时间复杂度 O(n)空间复杂度 O(1)。一个常见疑问为什么要让 cur 跳到 node1 而不是 node2因为 cur 永远扮演下一组节点的前驱角色。下一组的两个节点是 3 和 4它们的前驱是 1所以 cur 必须等于新链表中的 1这样下一轮循环里的 cur-next 恰好指向 3才能继续完成交换。这个位置感一旦建立起来往后写链表题会顺很多。3. 删除倒数第 N 个节点双指针的第一次实战3.1 先想清楚倒数第 N 个怎么定位普通思路是两次遍历第一遍算链表长度第二遍走到 len - N 的位置把它的 next 跳过一个节点。这个思路没问题也能通过但面试官通常会追问一句能不能只遍历一遍这时候就该双指针上场了。设计是这样的先用一个快指针 fast 从头开始先往前走 N1 步慢指针 slow 保持在起点不动。然后 fast 和 slow 以同样的速度同步前进。当 fast 走到链表末尾 nullptr 时slow 停下来的位置正好是待删除节点的前一个节点。为什么要让 fast 走 N1 步而不是 N 步因为我们要删除的是倒数第 N 个节点而删除动作的前置条件是找到它的前驱。如果 fast 只走 N 步slow 最终会停在倒数第 N 个节点本身删除它还得知道它前面是谁反而多了一步。多走一步让 slow 天然停在正确位置这是这道题最大的设计巧思。你可以拿一个 5 节点的链表验证一下删除倒数第 2 个节点。fast 先走 3 步到达第 3 个节点然后 fast 和 slow 同步走 2 步fast 到 nullptrslow 到达第 3 个节点也就是待删节点第 4 个的前驱。完美。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; } fast fast-next; // 再走一步使 slow 最终指向待删节点的前驱 while (fast ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; } };边界情况重点考虑两个一个是 n 等于链表长度的情况。比如链表长度为 1n1删除头节点。fast 从 dummyHead 走 1 步到节点 1再走 1 步到 nullptr然后 while 循环一次都不执行slow 停在 dummyHead。执行 slow-next slow-next-next也就是 dummyHead 直接指向 nullptr头节点被成功删除。如果没有虚拟头节点这里就要为删除头节点单独写分支了虚拟头节点的优势再次体现。另一个是 n 大于链表长度的情况。实际题目保证了 n 有效但面试中最好主动确认输入约束这也是一个加分沟通点。4. 链表相交把两个链表的问题变成对齐问题4.1 为什么不能直接比较节点值链表相交这道题题目给的是两个单链表让你找出它们相交的那个起始节点。注意它说的是节点相同不是节点的值相同。两个节点的值相等它们完全可以是两个独立的内存对象但两个链表一旦相交从相交节点开始往后两个链表共享的是一整段相同的节点序列。所以核心结论是比较的是指针地址不是值。最简单的做法是暴力双重循环对链表 A 的每个节点遍历链表 B 查找是否有相同的地址。时间复杂度 O(m*n)当然能过测试但面试时会被追问优化方案。更好的思路是双指针对齐法。4.2 对齐法的核心逻辑与代码两个链表相交之后从相交点到末尾的长度一定是一样的。既然如此两个链表本身的长度差一定集中在相交点之前。那么只要让长的那个链表先走掉这段差值两个指针就处于平齐状态——剩下的遍历中它们每一步都是同步的一旦遇到地址相同的节点就是交点走到 nullptr 都没遇到就是不相交。代码实现分两步先遍历求两个链表长度和尾节点再对齐移动。class Solution { public: ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* curA headA; ListNode* curB headB; int lenA 0, lenB 0; while (curA ! nullptr) { lenA; curA curA-next; } while (curB ! nullptr) { lenB; curB curB-next; } curA headA; curB headB; 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; } };我一直觉得这道题的思路特别像两个人在跑道上跑步一个起点靠后那就先让他往前跑一段直到两个人的起点对齐剩下就是同步跑相遇就是终点。这个对齐思路不只在链表相交里有用以后做数组滑动窗口、处理双指针问题时也能迁移。5. 环形链表 II赛跑模型与两个关键数学推导5.1 快慢指针怎么判环环形链表这道题先用快慢指针判断有没有环。fast 每次走两步slow 每次走一步。如果有环两个指针最终一定在环内相遇。为什么会相遇你可以想象两个人在环形操场跑步一个速度是另一个的两倍从同一起点出发快的迟早会追上慢的——但这里有个细节快的追上慢的之前它可能已经在环里绕了 n 圈。正因为环是闭合的无限循环之后两者必然重合。要特别说明的是 fast 步长为什么只能是 2。如果 fast 每次走 3 步slow 走 1 步在环长度和入口位置某些特定组合下fast 可能反复跨过 slow 而永远不相遇数学上就不保证收敛了。步长 2 是保证相遇的充分条件。这也是翻车高发区很多人觉得走 3 步更快就改了步长结果在特殊用例上报错。5.2 环入口的位置一道让人豁然开朗的推导判断有环只是第一问第二问要求返回环的入口节点。只靠快慢指针判断有环还不够还需要一个巧妙的指针操作来定位入口。先设几个参数头节点到环入口的距离为 x入口到相遇点的距离为 y相遇点继续走到入口的距离为 z。相遇时 slow 走了 xyfast 走了 xyn*(yz)n 表示 fast 在环内绕的圈数。因为 fast 的速度是 slow 的两倍所以2(x y) x y n(y z)化简得到x (n - 1)(y z) z当 n1 时x z。也就是说从相遇点再走 z 步到入口的距离等于从头节点走到入口的距离。这个结论的实操价值非常大相遇之后将一个指针移到头节点另一个留在相遇点两者每次都走一步它们再次相遇的那个节点就是环的入口。你可能会问如果 n 不是 1 呢公式也已经回答了不管 fast 提前绕了几圈从相遇点出发的指针走 x 步等价于走了 (n-1) 圈加 z 步而多绕的整圈对位置没有影响最终还是会停在入口。结论不受 n 的影响可以放心用。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) { ListNode* index1 head; ListNode* index2 fast; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; } };特别说一下 while 循环条件的写法fast ! nullptr fast-next ! nullptr。因为 fast 每次要走两步所以不仅要保证 fast 本身不为空还要求 fast-next 也不为空否则 fast-next-next 会访问空指针。这个判断顺序别写反先判断 fast 不为空再判断 fast-next 不为空。5.4 这道题真正难在哪环形链表 II 在 LeetCode 上的通过率并不高不是因为代码难写而是推导过程容易绕晕。很多人在看懂题解的一瞬间觉得哦原来如此但合上答案自己能完整写出代码的少之又少。我自己的方法是把推导过程完整写一遍不要只停留在记住结论。从 x z 这个公式入手自己设一组参数把公式代入验证一遍然后再写代码。至少在这道题上推导一次的印象比其他十道题都深。6. 链表题避坑指南与自查清单6.1 高频错误速查表错误类型具体表现应对策略丢节点修改 next 前没保存后继导致链表断裂动手前先画图标注需要保存的指针空指针访问对 nullptr 调用 -next 或解引用循环条件里先判空再访问成员虚拟头节点被忽略返回了 head 而非 dummyHead-next头节点被删时出错牢记返回的永远是 dummyHead-next快指针步长错误环形链表把 fast 步长改成 3特殊样例下标判环统一走 2 步不要画蛇添足死循环循环里 cur 没前进或前进方向错误每次循环结束后检查 cur 的位置变化6.2 我自己最受益的 debug 方法打印链表链表题逻辑一旦出错肉眼往往看不出问题。有个非常实用的土办法写一个链表打印函数在关键位置输出当前链表状态。void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout cur-val -; cur cur-next; } cout nullptr endl; }在每一步操作之后调用 printList你就能直观看到链表断在哪个位置、指针指向谁。两两交换那道题我就是靠打印确认了三步重连的先后顺序。打印会比调试断点快很多尤其适合数据量小、结构清晰的单链表题。另一个建议是每道题提交之前先手推一遍测试用例。不要直接 submit。Day04 这四道题我都建议在纸上至少走过一个链表长度为 4 或 5 的例子把所有边界情况删除头节点、链表长度为奇数、无交点无环提前在脑内跑一遍。比任何测试用例都好使。6.3 从 Day04 延伸出去的几道同类型题链表 part02 的四道题做完之后有几道题强烈建议趁热打铁练手思路完全同源LeetCode 21 合并两个有序链表用虚拟头节点双链表指针逐个拼接LeetCode 206 反转链表前驱指针与当前指针配合链表指针操作的又一基础LeetCode 25 K 个一组翻转链表两两交换的进阶版把两个一组换成K 个一组这些题能把 Day04 建立起来的虚拟头节点意识、指针顺序习惯、双指针思路巩固到肌肉记忆层面。我自己的安排是 Day04 当天先把四道题刷完第二天再花一小时刷这三道延伸题整体效率比一次性堆完高得多。我个人在刷完 Day04 后的一个体会是链表题本质上是在考你对状态的掌控力。数组题改一个元素影响范围是局部的链表题改一个指针影响的是整条链的走向。如果你能在动手前把每一步的指针状态在纸上画清楚链表在算法题里的难度其实是被高估的。Day04 这几道题全部吃透往后遇到反转链表、排序链表、链表成环这些变体你就不会慌了。

链表算法题通关指南：虚拟头节点与双指针实战

相关推荐

Cloudreve云盘系统源码部署与调优实战

Cloudreve云盘系统源码部署指南：从解压到跑通

大模型应用落地：从Demo到生产的AI工程化关键与实践

更多资讯

工业企业数据质量治理从救火到工程化：监控规则、责任矩阵与问题闭环落地指南

协同教学课程信息服务系统：SpringBoot+Vue毕设设计与实现

工业企业数据质量治理进阶：从清洗到体系化管控

汽车防撞梁优化设计开题报告：碰撞安全、仿真与多目标优化关键点

美赛数学建模实战：模型选择与代码实现指南

Claude Opus 5.5 焚诀实战：CLAUDE.md 与 Sub-agent 编排指南

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？