我是在从零开始刷“代码随想录算法训练营”的第四天完成的这天落下的是四道链表题力扣 24两两交换链表中的节点、19删除链表的倒数第 N 个结点、160相交链表、142环形链表 II。四道题我其实在不同时间零散刷过但按训练营的节奏集中再过一遍感受完全不一样——它们根本不是一个“链表杂题合集”而是一套从单指针到多指针、从同向双指针到交叉遍历、从直观解法到数学推导的完整进阶链路。这篇文章我会按当天的复盘顺序写下来把每道题的核心思路、代码、边界条件、常见坑都拆开讲。不管你是在跟训练营、自己刷 LeetCode还是准备面试这四道题都值得当成一个整体去练。1. 第四天的四道题其实是一条完整的链表训练主线1.1 链表题在算法面试里的定位链表是面试中“性价比”很高的题型。树和图动不动就是几百行的复杂结构链表题通常代码量不大但特别考验两件事对指针概念的敏感度、对边界条件的预判能力。很多候选人写链表题能跑通但一问“如果不允许修改链表结构怎么办”“如果链表长度为奇数呢”立刻就露馅了。第四天这四道题的价值就在这里。它们没有引入新的数据结构也没让你设计复杂算法每道题都只是在“操作指针”。但正是这种纯粹逼你把每一步都走清楚。1.2 四道题之间的递进关系我自己刷完之后的总结是这样一条链24 题核心是“多指针配合重连链表节点”训练的是对虚拟头结点dummy node的掌握以及指针断链、重连的顺序感。19 题核心是“快慢双指针形成固定步差”是双指针在链表中的第一个经典套路。160 题核心也是双指针但不再是同向走而是两条链表交叉遍历背后需要数学推导来证明正确性。142 题核心还是双指针升级为快慢指针的环检测同时要从相遇点反推环入口这是双指针在链表里的高阶应用。换句话说前三天的题覆盖了数组、哈希表、链表基础操作第四天则是在“链表操作”这个主题下把指针技巧从入门推向进阶。这一天的题目全部做完你对“指针在链表里能怎么玩”会有一个非常具体的认知。如果你也是刚进入算法训练营不久我建议不要只满足于 ACAccepted。每道题都静下心画一遍图、写一遍注释这比多刷十道简单题更有用。2. 两两交换节点为“指针一多就乱”打预防针2.1 为什么不直接操作头结点先看题目给定链表 1→2→3→4返回 2→1→4→3。要求不能简单交换节点里的值必须实际交换节点。新手最常见的错误是直接从头结点开始换。你会立刻发现一个问题要交换 1 和 2你需要知道 1 的前一个节点是谁但头结点没有前驱。于是要么单独处理头结点要么引入一个虚拟头结点。这里我强烈推荐虚拟头结点不仅仅是为了省一行代码而是因为它把“边界情况”变成了“普通情况”。ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead;这样处理之后头结点也是“有前驱”的节点了交换逻辑可以统一处理不需要 if (prev nullptr) 这种分支。2.2 三步重连法的执行细节交换 1 和 2第一步是要搞清楚需要几个指针。我当时画图之后发现至少需要三个指针才够cur指向待交换节点的前一个节点cur-next指向第一个要交换的节点例如 1cur-next-next指向第二个要交换的节点例如 2但只靠这三个指针不够。当你把 2 接到 cur 后面之后1 原来的 next 指向 2这个关系会被覆盖。为了避免丢失后面 3→4 的部分必须先保存第二个节点的下一个节点。这个表达很绕直接看代码更清晰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* tmp cur-next; // 保存节点1 ListNode* tmp1 cur-next-next-next; // 保存节点3 cur-next cur-next-next; // 步骤1cur 指向节点2 cur-next-next tmp; // 步骤2节点2 指向节点1 cur-next-next-next tmp1; // 步骤3节点1 指向节点3 cur cur-next-next; // cur 移动两位 } return dummyHead-next; } };步骤 1 执行完之后cur-next 已经变成节点 2 了所以步骤 2 里的 cur-next-next 其实指的就是节点 2 的 next把它改成指向节点 1。步骤 3 再把节点 1 的 next 接回节点 3。整个过程像在铁轨上拆一节车厢、换一节车厢、重新挂上顺序不能乱。如果还觉得晕画图是最快的。随便找张纸把 cur、1、2、3、4 画出来按这三步把箭头改掉一遍就明白了。2.3 最容易翻车的断链问题与 while 条件这个题有两个高频翻车点我都在训练营的讨论区看到了。第一个是断链。上面的代码如果没有 tmp1执行步骤 1 之后再去连节点 3 会发现找不到了。很多人的第一版代码都是这样报错然后一脸懵。解决办法就是提前保存。第二个是 while 条件。循环条件是 cur-next ! nullptr cur-next-next ! nullptr两个条件缺一不可。如果链表长度是奇数最后的“孤零零节点”不需要交换保持原样即可如果 cur-next 本身是空你还要访问 cur-next-next直接空指针异常。另外提醒一个代码顺序陷阱第一次交换完成后cur 应该向前移动两格指向下一对节点的“前驱”节点。我之前写过 cur cur-next结果是死循环因为 cur 只移动了一格下一次循环又处理了同一对节点。复杂度方面一次遍历时间 O(n)空间 O(1)。这里的 O(1) 指的是没有使用额外存储结构虚拟头结点只是一个固定开销的辅助节点。3. 删除倒数第 N 个节点快慢指针的“步差”是精髓3.1 两次遍历虽然简单却不够优雅19 题描述很直接删除链表的倒数第 N 个节点。最直觉的做法是先遍历一遍得到链表长度 len那么倒数第 N 个节点就是正数第 len - N 1 个节点再遍历一遍找到它的前驱并删除。时间复杂度 O(n)思路零门槛。那为什么还要学双指针因为面试官大概率会追问“能不能只遍历一遍”。更重要的是快慢指针这个套路在后续题目里反复出现比如 876 题求链表中间节点、142 题环形链表都是在同一个思想上演化的。3.2 步差设计与虚拟头结点的配合双指针思路很清晰让 fast 先走 n 步然后 slow 和 fast 一起走等 fast 走到链表尾部时slow 刚好停在倒数第 n 个节点上。但这里有一个关键细节删除节点需要找到它的前驱。也就是说我们希望 slow 停在倒数第 n1 个节点上而不是倒数第 n 个。解决办法是让 fast 先走 n1 步。我最初犯的错是 fast 只先走 n 步结果 slow 指向了要删除的节点本身删除逻辑变得非常别扭。所以正确写法长这样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-next ! nullptr) { fast fast-next; } // 此时 fast 和 slow 之间隔着 n 个节点 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; } };第一个 while 循环结束后fast 走了 n 步slow 还在 dummy两者之间隔着 n 个中间节点。当第二个 while 循环结束fast 到达最后一个节点时slow 恰好是倒数第 n1 个节点。这里也可以写成 fast 先走 n1 步再让 slow 动效果一样。我习惯用上面这个“先走 n 步再同步走”的版本因为它把“fast 到尾、slow 到前驱”的对应关系讲得更清晰。虚拟头结点在这个题里不是可有可无的点缀。假设链表只有一个节点要删除倒数第 1 个节点如果直接用 head 操作fast 先走一步就变成空指针了用 dummy 之后删除逻辑依然成立最后返回 dummyHead-next 即可。3.3 边界用例验证与复杂度刷链表题一定要养成代入边界用例的习惯。这个题我每次都会过这三个用例链表为空dummyHead-next 是 nullptrfast-next 为空直接返回 nullptr。删除头结点n 等于链表长度时fast 先走到最后一个节点slow 还在 dummy最后执行 slow-next slow-next-next正好把头结点删掉。链表只有一个节点n1第一个循环 fast 走一步到 null第二个循环不执行slow-next 被置空返回空链表。时间复杂度 O(n)空间复杂度 O(1)。这个题还有一个常见的变形不是删除倒数第 N 个而是寻找倒数第 K 个节点。思路完全一样只不过不用删除最后返回 slow 即可。4. 相交链表双指针交叉遍历背后的数学对等4.1 先想想朴素解法为什么能找到交点160 题是判断两条链表是否相交并返回交点。注意这里的相交是指节点地址相同不是节点值相同。朴素解法是哈希集合先把链表 A 的所有节点地址放进集合再遍历链表 B第一个出现在集合里的节点就是交点。时间 O(n)空间 O(n)。空间 O(n) 在面试里通常会被追问优化。很多人第一个想到的优化是“对齐尾部”先分别遍历两条链表得到长度让较长的链表先走差值步然后两条链表同步前进第一个相等的节点就是交点。这个方案正确但它隐含着一种“被动”——你得先知道两条链表各自的长度。双指针交叉遍历法更巧妙它连长度都不需要。4.2 双指针“走完自己走别人”的原理两个指针 pA、pB 分别从 headA、headB 出发pA 走自己的链表走完了就去走 headBpB 走自己的链表走完了就去走 headA两者都移动一步直到相等。如果两条链表相交它们会在交点相遇。如果不相交它们会同时走到 nullptr也满足相等退出循环。为什么假设 headA 的长度是 aheadB 的长度是 b公共部分长度是 c。pA 走到交点需要走 a (b - c) 步先走完自己的 a 步再到 headB 上走到交点前的 b-c 步pB 走到交点需要走 b (a - c) 步这两个表达式相等说明两个指针会在同一时刻到达交点。如果不存在交点公共部分长度 c 为零两个指针都会走 a b 步后同时到达 nullptr循环退出。“走完自己走别人”这一手本质上是把两条链表的长度差通过换路抵消掉了而且完全不需要提前知道长度。代码极其简洁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; } };我特别想提醒一点循环条件 pA ! pB 是无环链表里的一个“懒人写法”因为退出循环只有两种情况——相遇于交点或者同时为 nullptr。如果写成 while (pA-next ! nullptr) 这种形式处理空链表和不相交场景都会很麻烦。4.3 单链表相交、环形链表和这个题的关系做完 160 题之后你会注意到单链表相交和环形链表之间有很强的关联如果两条链表相交那么把 A 的尾节点接到 B 的某个节点上就会形成环。虽然 160 题本身不用环的思路但这个联想很重要。第四天真正做到 142 题时你会发现“快慢指针在环里相遇”的思想和 160 题的“两个指针走到同一个位置”是极其相似的。另外如果面试官问“能不能不用额外空间”你直接回答双指针交叉遍历如果问“为什么这样不会死循环”你就把上面的等式推导一遍。背结论很容易被识破能推导才是真会。5. 环形链表 IIFloyd 判圈法从相遇点到入口5.1 有环检测快慢指针为什么一定能相遇142 题要求找环的入口。前置问题是 141 题判断链表是否有环。快慢指针的做法是slow 每次走一步fast 每次走两步。如果有环两者必然在环内相遇。有环时二者一定会相遇的原因进入环之后fast 相对 slow 的速度差是 1 步/轮相当于 fast 每轮追赶 slow 一步。环的长度是有限的所以追赶一定能在有限轮内完成。这不是“碰巧”而是数学上必然。链表无环时fast 会先走到 nullptr直接返回。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 fast; ListNode* index2 head; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; } };5.2 入口推导这个结论必须能手推一遍先给出结论相遇之后把一个指针放回头结点另一个指针留在相遇点两者每次都走一步再次相遇的位置就是环入口。很多文章直接贴出这个结论就完事了。但面试官如果追问“为什么”你背答案就会卡壳。设链表中从头结点到环入口的距离为 a从环入口到相遇点的距离为 b从相遇点继续走到环入口的距离为 c。环的长度 L b c。slow 从出发到相遇走的距离是 a b。fast 从出发到相遇走的距离是 a b kL其中 k 表示 fast 在环内至少多跑了一圈k ≥ 1。由于 fast 速度是 slow 的两倍所以2(a b) a b kL化简得a kL - b即a (k-1)L c这个式子的意思是从头结点走 a 步到环入口的距离等于从相遇点先走 c 步到环入口再绕环转 k-1 圈的距离。所以把 index1 留在相遇点、index2 放回头结点二者每次都走一步最终一定会在环入口相遇。代码里 while (index1 ! index2) 退出时返回的就是入口节点。这个推导我在训练营里手推了不下五遍强烈建议你也推一遍。不是因为它多难而是只有自己推过现场被追问时才不会慌。5.3 面试追问环的长度如何求142 题常被追问的变形是已知有环怎么求环的长度方法是在判定相遇之后让一个指针停在相遇点另一个指针继续每次走一步同时计数。两个指针再次相遇时走过的步数就是环的长度。原因很简单从相遇点出发再次回到相遇点刚好走完一整圈环。因为二者速度相等第二个指针绕环一周时一定会再次碰到停在原地的第一个指针。如果你把 141、142、以及“环长度”这三个问题串下来相当于一个面试官把快慢指针的环检测考到了满分。142 题代码本身不难难的是把整个推导链条讲清楚。6. 串起来看刷完这四道题之后应该具备的三种能力6.1 指针重连时的“顺序感”四道题里最具体的技能是 24 题训练出来的指针重连顺序。链表操作本质上是一个“先保存、再断开、后重连”的过程。我自己总结的固定套路是三步发现哪些指针关系会被覆盖提前用临时变量保存按“先处理需要失去引用的节点再处理当前节点”的顺序执行赋值每次修改完画一次图确认链还没有断开。很多人写链表题依赖“把 LeetCode 题解背下来”但稍微变形就挂就是少了这个顺序感。顺序感只能靠画图养成没有别的捷径。6.2 双指针模型的识别能力19、160、142 三道题都是双指针但用法完全不同19 题是同向双指针固定步差160 题是交叉双指针遍历完一条换另一条142 题是快慢双指针速度差形成追赶。面试时看到“链表”两个字脑子里应该立刻浮现一个决策树要定位节点考虑同向双指针要比较两条链表考虑交叉双指针要判断环考虑快慢指针。这个识别能力不是看出来的是靠把一道题反复吃透练出来的。我在训练营里给自己定的规矩是每道题 AC 之后用一句话总结“这题用了什么套路、为什么用这个套路”四道题攒下来你会有一种突然开窍的感觉。6.3 边界条件从“靠运气”变成“靠清单”这四道题让我最受益的不是代码本身而是边界检查的习惯。我现在写链表题在提交之前一定会过一遍这个清单空链表只有一个节点两个节点奇数长度、偶数长度删除/交换发生在头结点、尾结点有环、无环、环入口在头结点。每次能把边界想全代码基本不会出大问题。这个习惯是刷链表题的额外回报它直接迁移到了后面的二叉树、回溯、动态规划里。第四天结束的那一刻我的感觉是链表题不是“背题”而是“练手”。当你把指针之间的相对关系摸清楚了LeetCode 上绝大多数简单、中等链表题都不会再让你卡住。这四道题作为训练营第四天的内容恰好把这个基础夯得很实。