很多人刷链表题最大的困惑不是写不出代码而是写出来了却说不清楚为什么这样写是对的。代码随想录第四天这四道题——24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II刚好把链表的进阶考点全部串起来了节点怎么换、双指针怎么定位、两条链表怎么找交点、环怎么判、环入口又怎么算。我刷完这一天的感受是基础操作题只是让你熟悉指针的用法这四道题才是真正把链表思维立起来的关键。这篇文章就当作我的一份详细复盘把每道题的思路、推导、代码和容易踩的坑都摊开来讲正在跟代码随想录刷题、或者准备算法面试的朋友应该都会用得上。1. 为什么说这四道题是链表学习的分水岭1.1 从增删改查到双指针思维的转变链表的前几道题比如反转链表、删除指定节点核心考察的是你能不能正确地改变指针指向。你只要把 prev、cur、next 三个指针理清楚再配一个循环基本就能解决。但到了第四天题目开始需要你在链表上定位某些特殊位置两两交换需要同时操作三组指针删除倒数第N个节点需要一次遍历精准找到位置链表相交需要处理两条长度不同的链环形链表II甚至要推导数学关系才能找到环的入口。这一步跨过去之后你会明显感觉到链表题的重点从指针会不会写变成了指针模型怎么设计。双指针、递归、数学推导这些在前三天很少出现的工具在这四道题里全部登场了。1.2 四道题的内在递进关系这四道题不是随便凑在一起的它们的难度和技巧是一层一层叠上去的24题考的是最基础的指针交接让你熟悉一次换两个节点时指针的保存顺序19题引入双指针用快慢指针的距离差来定位倒数位置02.07题把双指针从一条链扩展到两条链并且需要你想到怎么消除两条链的长度差142题则是双指针和数学证明的极致结合不仅要判断有没有环还要精确算出环的入口。把这四道题按顺序刷完你对双指针的理解会是递进式的而不是零散的。这也是为什么很多刷题攻略会把它们放在同一天。2. 24. 两两交换链表中的节点先搞懂指针怎么换再谈写代码2.1 题目本质与迭代思路题目要求把链表中每两个相邻节点交换位置而且明确规定不能单纯改变节点的值必须实际修改节点的指向。比如1-2-3-4交换后变成2-1-4-3。我第一次做这道题的时候第一反应是交换两个节点不就和交换两个变量一样吗用三个临时变量不就完事了但真正动手才发现单链表的特性决定了你只能从前往后访问没法回头。交换1和2之后下一步需要处理的是3和4而这时候cur指针应该停在1的位置因为1-next现在指向的是4循环才能继续走下去。迭代法的核心思路是每轮处理一对节点用一个前驱指针cur指向这对节点的前一个位置。假设相邻两个节点是first和second交换之后first变成第二个second变成第一个然后让cur指向新的第二个节点也就是原来的first继续下一轮。2.2 哑节点为什么是必需品如果不用哑节点头节点会在第一次交换中变成第二个节点这会让头节点的处理逻辑和其他节点不一致代码里就得多写一个特判。比如1-2-3-4交换后头节点变成了2如果你返回的是原来的head那结果就是错的。所以我在链表题里养成了一个习惯只要头节点可能被修改就无脑加哑节点。哑节点的next指向真正的头节点最后直接返回dummyHead-next不管怎么交换头节点都能正确拿到。这个习惯在 19 题、142 题里同样适用。24 题的迭代代码是这样的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; ListNode* nextGroup second-next; // 下一组的起点 cur-next second; // 前驱指向新的头节点 second-next first; // 第二个节点指向第一个 first-next nextGroup; // 第一个节点接上下一组 cur first; // cur 移动到新的前驱 } return dummyHead-next; }2.3 借助三个临时变量的原因你可能已经注意到我保存了first、second、nextGroup三个指针。为什么不直接操作cur-next和cur-next-next因为一旦执行了cur-next second原来的first节点就只能通过second-next访问到了如果之后还想用first做操作就必须提前保存。这就是链表操作里最常见的坑之一指针在赋值之后原来的引用可能就失效了。尤其是连续多次修改next指针时如果没有提前把要用到的节点存下来等到后面再取取到的可能已经不是你想的那个节点了。建议你拿到代码之后自己在纸上画一遍1-2-3-4的交换过程把每一行代码执行后指针指向的变化写出来。画完一遍你会彻底理解为什么需要这三个临时变量。2.4 递归写法与循环终止条件这道题也可以用递归做核心是找到最小子问题两个节点交换然后递归处理剩下的链表。ListNode* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead head-next; head-next swapPairs(newHead-next); newHead-next head; return newHead; }递归的终止条件是head nullptr或head-next nullptr分别对应空链表和只剩一个节点的情况。递归的返回值需要接到上一层的head-next上这一步很容易漏。我见过不少朋友写递归版代码看起来没问题但返回的头节点不对原因就是没有把递归结果接回原来的链表。迭代法的循环条件是cur-next ! nullptr cur-next-next ! nullptr这个条件同时处理了偶数节点和奇数节点两种情况。链表长度为奇数时最后一个节点不需要交换循环自然退出。时间复杂度是 O(n)空间复杂度 O(1)递归为 O(n) 栈空间。3. 19. 删除链表的倒数第N个节点一次遍历的经典双指针范式3.1 为什么倒数第N个需要双指针这道题看起来很简单先遍历一次求出链表长度再遍历一次走到length - n的位置删除节点。但很多面试官会追问能不能只遍历一次要一次遍历找到倒数第 N 个节点需要解决的核心问题是不知道该删除的位置在哪里因为链表长度未知。这时候双指针就派上用场了。让快指针先走 N 步然后快慢指针同步前进当快指针到达末尾时慢指针刚好停在待删除节点的前一个位置。这个思路的关键在于快慢指针之间始终保持 N 个节点的距离。快指针先走 N 步时两个指针之间的距离是 N之后同步走这个距离不变。当快指针走到最后一个节点时慢指针自然就落在倒数第 N1 个节点上也就是待删节点的前驱。3.2 快指针先走 N 步而不是 N-1 步有一个细节值得单独拎出来说为什么快指针要先走 N 步而不是 N-1 步假设链表的长度为 L我们要删除倒数第 N 个节点。倒数第 N 个节点从头部数就是第L-N1个节点它的前驱是第L-N个节点。快指针先走 N 步后距离链表末尾还有L-N步。之后快慢指针同步走慢指针从哑节点出发也会走L-N步于是慢指针落在第L-N个节点上——正好是待删节点的前驱。如果让快指针先走 N-1 步最终慢指针会落在待删节点本身删除操作就没法直接做了。我的建议是不要死记走 N 步还是 N-1 步而是每次做之前先在脑子里模拟一个具长的链表比如1-2-3-4-5N2。快指针先走 2 步到节点 3然后同步走快指针到节点 5 时慢指针在节点 3删除节点 4正确。3.3 边界条件删除头节点与删除尾节点这道题最容易出错的是删除头节点的情况。比如1-2-3N3要删除的是节点 1。如果不加哑节点删除头节点需要单独处理head head-next。但头节点什么时候会被删取决于 N 和链表长度的关系写个 if 判断总觉得不够干净。加了哑节点之后所有删除操作统一用slow-next slow-next-next不需要任何特判。删除尾节点反而是最简单的N1时快指针先走 1 步到节点 2然后同步走快指针到节点 5 时慢指针在节点 4直接删除节点 5。链表只有一个节点时哑节点也能正确处理快指针先走 1 步到 nullwhile (fast-next ! nullptr)不进入慢指针还在哑节点删除的是真正的头节点。3.4 完整代码与复杂度ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; while (n-- 0) { fast fast-next; } while (fast-next ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; }时间复杂度 O(n)空间复杂度 O(1)。这道题刷完之后我顺手把找到链表倒数第 N 个节点也练了一遍其实就是把删除操作去掉其他代码完全一样。3.5 双指针的另一种形态找链表中间节点19 题的双指针是同速前进只是出发时间不同。还有一种常见变体快指针每次走两步慢指针每次走一步快指针到达末尾时慢指针刚好在中间。这个技巧在判断回文链表、链表排序等题目中经常用到。我在刷 19 题的时候会同时把这两种双指针形态放在一起对比因为它们其实是一个模板要么距离差固定要么速度差固定目的都是让慢指针到达某个特定位置。4. 面试题 02.07. 链表相交两条链表的殊途同归4.1 相交的本质地址相同不是值相同这道题的要求是判断两个链表是否相交如果相交返回相交的起始节点。有一个很重要的前置概念链表相交指的是两个链表存在同一个内存地址的节点而不是两个节点的val值相等。很多初学者会在这里翻车比较节点值来判断是否相交。但实际链表题中节点值是可以重复的。比如链表 A 是1-2-3链表 B 是9-2-3节点 2 的值相同但它们是两个不同的节点内存地址不同完全不相交。所以这道题百分百要比较指针地址只能在ListNode*这个层面做相等判断。题目背景里还有个细节两个链表可能长度不同但相交之后的部分是共用的也就是说从相交节点开始到链表尾部它们共享同一条链。这个特性是后续所有解法的基础。4.2 哈希表法最直观但空间开销大最容易想到的思路是用哈希表遍历链表 A把每个节点的指针存入哈希表再遍历链表 B逐个检查当前节点是否已经在哈希表中第一个命中的就是相交节点。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { unordered_setListNode* visited; ListNode* cur headA; while (cur ! nullptr) { visited.insert(cur); cur cur-next; } cur headB; while (cur ! nullptr) { if (visited.count(cur)) return cur; cur cur-next; } return nullptr; }时间复杂度 O(mn)空间复杂度 O(m)。这个解法胜在思路简单、不容易出错但面试官通常会追加一句能不能把空间复杂度降到 O(1)这时候就需要双指针登场了。4.3 双指针法一先消除长度差经典的双指针解法是先计算两条链表的长度让较长的那条先走差值步然后两条链表同步前进第一个相同的指针就是交点。这个解法的逻辑很直观如果两条链表相交从相交节点到末尾的长度是相同的。长度差只存在于相交之前的部分。让长的那条先走差值步相当于把起跑线对齐之后两条链表同步走就能在相交节点相遇。4.4 双指针法二拼接链表殊途同归第二种双指针写法代码更短但理解起来需要一点推导。思路是这样的指针 pA 从 headA 出发走完 headA 之后跳到 headB 继续走指针 pB 从 headB 出发走完 headB 之后跳到 headA 继续走。两条指针走的路程相同如果链表相交它们必然会在交点相遇。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA nullptr ? headB : pA-next; pB pB nullptr ? headA : pB-next; } return pA; }为什么这种写法是对的假设链表 A 相交前长度为 a链表 B 相交前长度为 b公共部分长度为 c。pA 走完 A 的长度是 ac然后从 B 头部开始走走到交点时又走了 b。总共走了 abc。pB 的路径同理也是 abc。两条指针在路程相同的情况下最终指向同一个节点这个节点就是交点。如果两条链表不相交呢pA 会走完 abpB 也会走完 ab最终它们都指向 nullptr循环退出返回 nullptr。注意这里的pA nullptr表示 pA 已经走完了自己那条链需要跳到另一条链的头部这个跳转逻辑保证了总路程相同。4.5 与环形链表II的思想呼应刷完 02.07 这道题再回头看 142你会发现它们之间存在共通点都是通过让两个指针走相同路程从而在某一点相遇。02.07 是让 pA、pB 走完两条链表的总长度142 是让快慢指针在环内相遇再从头走一个特定的距离。很多人在刷题时容易把每道题当独立的题目去记但这两道题放在同一天刷目的就是让你体会到双指针消除路程差这个模型的普适性。如果你能自己总结出这一层那第四天的题就算真正刷透了。5. 142. 环形链表II快慢指针的数学硬核时刻5.1 判环与找入口之间的差距142 题要求两件事判断链表有没有环如果有则返回环的入口节点。只判环很容易快指针每次走 2 步慢指针每次走 1 步如果两个指针相遇就说明有环。但找到环的入口才是这道题的真正难点它需要一点数学推导。我先说结论当快慢指针在环内相遇后用一个新指针从头节点出发另一个指针从相遇点出发两个指针每次走 1 步它们相遇的位置就是环入口。这个结论如果只是背下来过几天就会忘。但如果你自己推导一遍就再也不会忘了。5.2 为什么快慢指针一定会在环内相遇在推导入口之前先回答一个基础问题为什么有环的情况下快指针走 2 步、慢指针走 1 步两个指针一定会相遇当慢指针进入环的时候快指针可能已经在环里绕了好几圈了。但从快指针的角度看它相对于慢指针的速度是2-11步/次也就是说每次移动快指针都会比慢指针多前进 1 个节点。环的长度是有限的快指针以每次 1 个节点的相对速度追赶慢指针必然会在有限次移动后追上。又因为快指针每次只比慢指针多走 1 步它不会跳过慢指针所以是必定相遇而不是可能相遇。如果快指针每次走 3 步相对速度是 2 步/次在环长度是偶数的情况下快指针可能正好跳过慢指针导致永远追不上。这也是很多教材规定快指针走 2 步而不是 3 步的原因。5.3 相遇后如何找回入口完整的数学推导设链表头节点到环入口的距离为 a环入口到快慢指针相遇点的距离为 b环的周长为 c。慢指针从链表头开始走到相遇点时一共走了a b步。快指针从链表头开始走到相遇点时可能已经在环里绕了 k 圈所以它一共走了a b k*c步。因为快指针的速度是慢指针的 2 倍所以2 * (a b) a b k*c化简得a b k*c再变形a k*c - b这个式子的含义是从链表头走到环入口的距离 a等于从相遇点继续走k*c - b的距离。也就是说如果一个指针从头节点出发另一个指针从相遇点出发两者同时以每次 1 步的速度前进它们会经过相同的路程最终在环入口相遇。因为k*c - b可以理解为绕 k 圈后回到某个位置再往回走 b起点是相遇点绕 k 圈后回到相遇点再走c - b到达入口。所以这段路程的终点确实是环入口。代码实现就是基于这个结论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; }注意入口查找的循环条件while (index1 ! index2)因为入口一定存在所以不需要额外的终止条件。如果题目要求判断无环的情况只需要在快指针或快指针的 next 为空时返回 nullptr 即可。5.4 推导过程中常见的错误理解有几个地方特别容易出错我当初也踩过第一快慢指针的相遇点不一定是环入口。很多初学者想当然地认为快慢指针相遇的地方就是环的入口这完全不对。相遇点只是推导中的一个中间变量真正的入口需要通过第二次同步走才能确定。如果直接把相遇点当作入口返回大概率是错的。第二a b k*c中的 k 是一个未知数不需要求出来。推导的最终目的是找到从头节点出发的指针和从相遇点出发的指针能否在入口相遇这一个结论k 的具体值不影响代码实现。第三无环链表下快指针的判断条件。我见过有人写成while (fast ! nullptr)但快指针每次走两步如果fast-next已经是 nullptr 了下一步fast-next-next就会报空指针。所以第二个条件是fast-next ! nullptr这两个都不能少。5.5 由 142 引出的常见变形这道题刷完之后可以顺手做几个变形练习求环的长度快慢指针相遇后让一个指针原地不动另一个指针继续走再次相遇时走过的步数就是环长。判断两个链表是否相交可以把链表 A 的尾节点接到链表 B 的头节点然后判断链表 B 是否有环如果有环说明两个链表相交。这个变形正好把 02.07 和 142 串联起来了。找有环链表的某个特定节点有些变体会要求你返回环内的某个节点理解了入口推导之后这类题通常也能迎刃而解。6. 四题刷完之后的实战收获6.1 双指针的三种形态刷完这一天我自己把双指针在链表里的用法归纳成了三种形态分享出来供你参考形态特征典型题目同速错位两个指针速度相同但出发时间不同形成固定距离差19. 删除倒数第N个节点异速追赶两个指针速度不同利用速度差在环内相遇142. 环形链表II同步走不同链两个指针分别走两条链表通过拼接消除路程差02.07. 链表相交这三种形态不是孤立的知识点它们的底层逻辑都是用两个指针之间的距离或路程来定位特定节点。一旦你建立了这个认知框架遇到新的链表题时就更容易往这个方向思考。6.2 哑节点的使用边界我在 24 题、19 题里都加了哑节点142 题其实也可以加一个虽然对结果没有影响。我的使用经验是头节点可能被修改、被删除、被交换时加哑节点几乎总是对的只是遍历链表、不修改链表结构时不需要哑节点递归写法中哑节点通常不是必需的递归本身就能处理好头节点的逻辑。哑节点最大的价值不是省代码而是让你少写很多 if 分支减少边界条件出错的可能性。我见过太多人栽在删除头节点和交换头节点这种地方一个哑节点能解决的问题何必用 if 去硬处理。6.3 我自己的复盘方法坦率说这四道题我第一遍刷的时候24 题的迭代写法卡了将近一个小时142 题的数学推导看了两遍才真正理解。后来我发现一个非常好用的复盘方法每题刷完后把链表结构画出来然后手动模拟代码的每一步指针变化。这个方法看起来很笨但效果出奇的好。因为链表题的 bug 大多数不是逻辑层面的而是指针细节层面的。手动模拟两三次之后你对哪个指针先保存、哪次赋值会覆盖原来的引用这类问题会形成一种直觉下次写代码时出错率会大幅下降。6.4 给你的一点建议如果你正在刷代码随想录第四天我建议你按 24 → 19 → 02.07 → 142 的顺序来不要跳着刷。这四道题对指针操作和双指针的要求是逐渐升级的按顺序刷能建立更自然的能力阶梯。刷完之后试着不看代码把每道题的思路和关键步骤用几句话讲给自己听讲不出来就说明还没真正掌握。聊到这里我最后分享一个小习惯链表题写完后我会自己造几个特殊输入测一下——空链表、只有一个节点、奇数个节点、偶数个节点、要删头节点的极端场景。这个习惯帮我抓住了很多一眼看不出来的 bug也让我在面对面试官追问边界情况时不至于慌。今天的四道题每一道都可以用这套测试方法过一遍。