算法训练营到第四天题量开始上强度了。前三天还在熟悉数组、哈希表、双指针的基本套路第四天直接排在面前的是四道链表题24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。光看题单有点慌但老老实实做完一遍之后我发现这四道题放在同一天不是巧合它们其实在反复训练同一种能力在改链表结构的时候你怎么保证不丢节点、不越界、不漏解。如果你也是刚开始系统刷链表题或者刷过这几道题但总觉得“代码能过思路说不清”这篇文章应该能帮你把这些题串起来。我会按当天刷题的完整顺序逐题拆解题思路、写下能直接跑的代码然后把每道题背后最容易踩的坑和面试时怎么把思路讲明白一起复盘掉。1. 第四天四道题为什么值得放在一起先说结论这四道题不是“四道独立的题”它们是链表操作里两个核心技能的组合演练——虚拟头节点和双指针/快慢指针。1.1 四道题的考点对照把四道题放在一张表里看脉络很清楚题目核心考点推荐技巧时间复杂度 / 空间复杂度24. 两两交换链表中的节点相邻节点的指针重排虚拟头节点 三个指针O(n) / O(1)19. 删除链表的倒数第N个节点倒数定位一趟扫描快慢指针制造长度差O(n) / O(1)面试题 02.07. 链表相交判断两条链是否共用节点长度对齐 / 互换路径双指针O(n) / O(1)142. 环形链表II环判断 环入口定位快慢指针 数学推导O(n) / O(1)四道题的空间要求都是 O(1)也就是说你不能靠哈希集合、数组辅助来偷懒。这就决定了它们的共同难点你只能用有限几个指针在链表的节点之间腾挪同时保证任何时刻都不会把还没访问到的部分弄丢。1.2 贯穿全天的两条主线第一根主线是虚拟头节点。24 题和 19 题都需要 dummyHead。原因很简单这两题都可能动到真正的头节点。两两交换会让原头节点变成第二个节点删除倒数第 N 个节点时如果 N 等于链表长度删的就是原头节点。没有虚拟头节点你就得为“头节点变了”写一堆 if 特判。有了 dummyHead一切操作从 dummy 开始最后统一返回dummyHead-next代码干净不少。第二根主线是双指针。19 题用快慢指针定位倒数第 N 个节点02.07 题用两个指针分别走两条链来抹平长度差142 题用快慢指针判断环并用数学推导找入口。你会发现“单链表只能往前走”这个限制让很多问题从“往回看”变成了“让两个指针站在不同位置制造出距离差”。1.3 动 next 之前先备份这是链表题最容易被忽略的常识但第四天四道题把这个问题放大得非常明显。链表的节点之间只有 next 指针相连你改了一个节点的 next原来的后继就丢了。除非你已经事先拿另一个指针把它接住了。我习惯把它类比成数据结构里的进程切换你先保存现场才能安全切换。链表题里几乎所有的翻车现场都是因为“先改了一个 next然后又想用这个节点再往回找”结果指针早飞了。2. 24. 两两交换链表中的节点最考验指针重排节奏感的题2.1 先看一眼题目题干很直白给定一个链表两两交换其中相邻的节点并返回交换后的链表。比如 1-2-3-4交换后变成 2-1-4-3。如果节点总数是奇数最后一个节点保持原样比如 1-2-3交换后是 2-1-3。注意这道题要求的交换是节点本身不是把节点的值换一下。有同学图省事直接遍历链表把每两个节点的 val 交换这种写法在力扣上也能过但面试时基本会被追问“如果节点自带很多字段或者有其他指针指向这些节点你只换值还成立吗”。链表操作题的通用约定就是动指针不改值。所以还是老老实实做指针重排。2.2 迭代写法的核心三个指针互相配合我的做法是用虚拟头节点加三个工作指针cur指向当前一组待交换节点的前一个节点firstcur-next这一组的第一个节点secondcur-next-next这一组的第二个节点完整代码如下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; // 第一步让 first 指向下一组的开头防止后续节点丢失 first-next second-next; // 第二步second 翻到 first 前面 second-next first; // 第三步让前一组接上新的头节点 second cur-next second; // 第四步cur 前进到下一组的前驱也就是交换后的 first cur first; } return dummyHead-next; }关键就在这四步的顺序。为什么第一步必须是first-next second-next因为你要先把剩下的后半段链表“接住”。如果不做这一步等到second-next first时原来 second 后面的那一整段就彻底找不到了。第二步让 second 回头指向 first第三步把前一个节点 cur 连接到新的头节点 second最后 cur 移到第一节点。2.3 循环条件和 cur 的更新时机循环条件必须是cur-next ! nullptr cur-next-next ! nullptr。两个判断缺一不可没有cur-next就不能取cur-next-next会空指针只有cur-next而没有cur-next-next说明剩下一个节点无法配对。cur 的更新也容易错。我见过有人写成cur cur-next这实际上会指向 second。但第二组的前驱应该是这一组交换后的第二个节点也就是原来的 first。举个例子1-2-3-4第一轮交换后链是 2-1-3-4下一轮要处理的是 3 和 4它们的前驱是 1而不是 2。所以必须cur first。2.4 为什么我更推荐迭代写24 题也可以递归写代码更短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; }递归写法的优势是逻辑清晰几乎不用管指针顺序。但它的递归深度是 n/2对于很长的链表会占用调用栈更重要的是这道题最优解明显是 O(1) 空间迭代写法更能体现这一点。面试如果问空间复杂度递归版容易被追问“这里递归栈不算空间吗”。所以我的建议是练到能不看代码写出迭代版再去体会递归版。2.5 这题的三个典型翻车点第一循环条件少写一个cur-next ! nullptr只有两个节点时直接解引用空指针。第二四步交换顺序搞错最常见的错误是先cur-next second再回头处理 first 和 second 的关系这时候很容易丢掉后续链表。第三忘记用虚拟头节点最后 return 的是原来的 head但 head 早就变成第二个节点了白做半天。这三类错误我在带算法小组时见过无数次基本都是同一个根源对这一步操作之后“哪个指针还能访问到哪个节点”没想清楚。3. 19. 删除链表的倒数第N个节点一趟扫描靠的是“长度差”3.1 为什么不能直接按倒数去找单链表只有 next 指针你站在头节点时根本不知道倒数第 N 个节点在哪。最朴素的思路是先遍历一遍得到链表长度 L再走 L-N 步到目标节点的前驱做删除。这需要两趟扫描肯定能过但题目描述里明确说“一趟扫描完成”。面试中能直接交出一趟扫描方案通常会让面试官觉得你对链表更熟悉。说白了倒数第 N 个节点就是“离末尾还有 N 步”的节点。那我们只需要让一个指针先走出去 N 步另一个指针从同一起点慢悠悠地走当先走的那个指针碰到链表末尾时后走的那个指针离末尾也正好是 N 步。这就是快慢指针制造“长度差”的核心。3.2 快慢指针怎么停在待删节点的前一个删除操作需要找“待删节点的前驱”。如果让 slow 直接指向待删节点删起来还要临时往前找很麻烦。所以标准做法是让 slow 停在倒数第 N1 个节点。我习惯让两个指针从虚拟头节点出发fast 先走 N 步然后 fast 和 slow 一起走但停止条件不是 fast 到 nullptr而是fast-next nullptr。这样 slow 会自动停在待删节点的前一个。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; // fast 先走 n 步 while (n-- 0 fast ! nullptr) { fast fast-next; } // 一起走直到 fast 到达链表末尾的前一个节点 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // slow 此时指向待删节点的前一个 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; return dummyHead-next; }为什么停止条件用fast-next ! nullptr因为 fast 先走了 N 步之后两个指针之间的差距正好是 N。等到 fast 站在最后一个节点时slow 和 fast 之间仍然隔着 N 个节点也就是 slow 的下一个节点才是要找的倒数第 N 个节点。如果停止条件写成fast ! nullptr那 slow 会直接停在待删节点上删除前还得再找个临时指针往前处理。3.3 边界情况全测一遍用几个典型用例手动过一遍n 等于链表长度。比如 1-2-3n3。fast 从 dummy 先走 3 步正好走到最后一个节点 3。此时fast-next nullptr循环一次都不执行slow 停在 dummy。删除的就是slow-next即原头节点 1。dummyHead 在这里的价值体现得淋漓尽致。n1删除最后一个节点。fast 先走一步走到节点 1然后 fast 和 slow 一起走直到 fast 走到节点 3最后一个节点slow 停在节点 2删除节点 3。链表只有一个节点n1。fast 从 dummy 走一步到节点 1fast-next nullptrslow 停在 dummy删除节点 1返回 nullptr。还要提一个工程细节LeetCode 保证 n 在有效范围内但如果你在真实工程或者面试手写时遇到 n 大于链表长度的情况要先问清楚输入边界最好先统计长度做校验或者把 n 的有效性作为前提条件明确说出来。3.4 一趟扫描的复杂度很干净O(n) 时间O(1) 空间一趟扫描完成。这道题真正的得分点不是代码量而是能不能说清楚“fast 先走 n 步”这个设计的原因——它可以类比成跑步比赛让对手先跑十米你俩同速等对手到终点时你离终点正好十米。把抽象的距离差转换成起跑线偏移链表题的很多问题都能这样想通。4. 面试题 02.07. 链表相交交点比的是地址不是值4.1 这道题最容易踩的认知陷阱题目描述给你两个单链表的头节点找出两个链表相交的起始节点。所谓相交是指从某个节点开始两条链表的 next 指针指向了同一批节点也就是它们“共用”了后半段。很多人一上来就用节点值判断这是大坑。不同节点的 val 完全可能相等但它们在内存中是不同对象。链表相交判断的唯一标准是节点地址是否相同在代码里表现为两个指针是否相等。所以下面的判断一定是curA ! curB而不是curA-val ! curB-val。4.2 解法一长度对齐好想也好写相交链表的公共尾部长度相同所以交点之前的私有部分长度差正好等于两条链表的长度差。做法是先分别统计两条链的长度把较长链表从头开始多走|lenA - lenB|步然后两个指针同步前进第一次遇到地址相同就是交点走到末尾都没有说明不相交。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { 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; int diff lenA - lenB; if (diff 0) { while (diff-- 0) curA curA-next; } else { diff -diff; while (diff-- 0) curB curB-next; } while (curA ! nullptr curB ! nullptr curA ! curB) { curA curA-next; curB curB-next; } return curA; // 不相交时 curA 为 nullptr }这种写法最直观。先算长度长的先走差值两边对齐后同步走。面试中如果你先给出这个解法对方基本不会觉得你有问题。4.3 解法二走完自己的路再去走对方的路更巧妙的写法是双指针互换路径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 同理。如果两条链相交pA 总共走了“链A私有部分 公共部分 链B私有部分”的距离pB 走了“链B私有部分 公共部分 链A私有部分”。这两段总距离相等所以它们会在某个时刻同时到达同一个节点——那就是交点。如果完全不相交最后会同时走到 nullptr退出循环返回 nullptr。第一次听这个思路的人很容易懵所以我一般会先讲长度对齐再补充“如果不想先算长度可以用互换路径原理是把两条链的长度差抹平”。两道题都是 O(n)/O(1)选哪种看你对哪个更有把握面试时不要为了一味炫技选一个自己讲不清楚的写法。4.4 哈希表能解但不是这题的目标解法用哈希集合存下链A的每个节点再遍历链B判断节点是否在集合中逻辑很简单而且代码不容易错。但它需要 O(n) 的额外空间。链表系列题的高阶考察点之一就是“你能不能不用额外数组/哈希表只靠指针操作把问题解决”。所以哈希表版本可以自己在本地验证用面试时建议还是讲上面的双指针方案。5. 142. 环形链表II一道题考两个模型142 题是四道题里最“难”的一题难点不在于代码长而在于它分成两个问题先判断有没有环再找到环的入口。两个问题都依赖同一个快慢指针框架但第二个问题需要做一点数学推导。5.1 判断有环快指针为什么每次走两步经典做法是 fast 每次两步slow 每次一步。如果链表无环fast 会先走到 nullptr如果有环fast 先进环在环里绕圈slow 后进环两者最终会相遇。为什么不选一次三步、四步因为快慢指针的相对速度不同。fast 是 slow 的两倍时每走一轮fast 相对 slow 多走一个节点。想象把 slow 看成静止的fast 在以“每轮一个节点”的速度追它在环上不可能跳过它必然追上。如果 fast 一次走三步相对速度是 2fast 可能从 slow 头上“跨过去”相遇的保证就没了。这就是步长选 2 的根本原因。5.2 相遇之后怎么找环的入口假设链表头到环入口的距离是 a入口到 fast 和 slow 相遇点的距离是 b相遇点继续走到入口的距离是 c那么整个环长 L b c。两个指针从链表头出发到相遇点slow 走过的路程是 a b。fast 的路程是 a b kL其中 k 是 fast 在环里比 slow 多绕的圈数。因为 fast 的速度是 slow 的两倍所以2(a b) a b kL两边同时消掉 a b得到a b kL稍微整理一下a kL - b (k - 1)L c这个式子说明从链表头到环入口的距离 a等于从相遇点继续走 c 步再加上若干整圈。也就是说如果同时放两个指针一个从链表头出发一个从相遇点出发两者都每次走一步走完各自的 a 步和 c 步之后会在环入口相遇。因为后面那一整圈一整圈的部分不会改变它们的相对位置最终影响的都是 c。代码落地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; // 或者 slow while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; }注意第二次循环里两个指针都必须改成每次一步千万别让其中一个继续保持两步的速度否则它会在环里绕来绕去永远不会和 index1 在入口对齐。5.3 一个常被追问的细节slow 进环后几圈内会被追上很多聪明的读者会问fast 先进环绕了那么多圈slow 才慢慢进来万一 fast 跑到 slow 后面很远了怎么办其实不用担心。设链表头到环入口距离为 aslow 从 head 走到入口需要 a 步这期间 fast 走了 2a 步也就是 fast 进入环后已经多走了 a 步的距离。在环内fast 领先 slow 的距离最多不到一个整环 L。由于 fast 相对 slow 每轮靠近 1 个节点它最多花不超过 L-1 轮就能追上 slow。换句话说slow 进环之后还没走满一圈就会被 fast 赶上。5.4 代码落地的常见错误第一while 条件里面忘了判断fast-next ! nullptr导致 fast 已经走到末尾后再取fast-next-next直接空指针。第二判断有环之后把 index2 设成 fast 没问题但有人会把 index2 改成 fast-next那就偏移了一个节点结果整个推导对不上了。第三找到相遇点就返回相遇点忘了题目要的是环入口。相遇点是快慢指针第一次重合处不是环入口两者一般不重合。第四有人在第二次循环里用while (index1 ! index2-next)把终止条件也写歪了我建议统一写成while (index1 ! index2)每次各自向前一步逻辑最不容易乱。6. 复盘第四天的收获远不止会做四道题刷完这四道题如果只是“AC 了”那收获会打折扣。真正有价值的是把这四道题里反复出现的几个思维模型提炼出来以后遇到其他链表题能直接用。6.1 “动 next 前先备份”是所有链表修改题的通用法则24 题里要先让 first 指向 second-next再改 second-next19 题里删除节点前先记录 toDelete。这两个操作的本质一模一样你想断开一条链之前必须先把断口后面的部分接到一个变量手上。我刷链表题到现在凡是修改型题目动笔之前都会问自己一句这一步操作之后原来那个后继节点还能从哪个指针访问到如果答不出来说明马上要丢节点了。6.2 “差值对齐”不知不觉串起了三题19 题是 fast 先走 n 步制造 n 的差距02.07 题是长链表先走长度差让两条链尾部对齐142 题是 fast 相对 slow 多走整圈数。这三个解法本质上都是同一个思想单链表没有回头路我们就用两个不同起跑线的指针把“位置差”变成可见的步数差。一旦把这个思想想明白很多看起来完全不同的链表题底层其实是同一套东西。6.3 四道题的整体对照题目一句话关键点最容易错的地方24 两两交换四步指针重排第一步先接住后续节点cur 更新成 cur-next19 删除倒数Nfast 先走 n 步slow 停在待删前驱停止条件用错02.07 链表相交比地址不比 value长度对齐或互换路径用 val 判断交点142 环形链表II快慢指针判环 数学推导找入口忘记环入口不是相遇点6.4 给刷题者的一条实操建议如果你现在正在跟某个算法训练营或者自己刷题我建议不要只顾着“背答案”而是每做完一道题合上代码用三句话把思路讲给自己听。比如 19 题你要能说清楚“fast 先走 n 步制造差距然后同速走fast 到末尾时 slow 正好在倒数第 n1 个节点”。如果你能不用代码把这句话讲明白才算真的懂。我个人带算法小组的时候发现链表题写得慢的人九成不是不知道思路而是不敢动 next怕把链表改坏了。这四道题恰恰把这个问题暴露得很彻底24 题要连续改三个 next19 题要删节点02.07 题要处理两个头的对齐142 题要在环里反复绕。练完之后最大的收获不是四个解法而是在动手改任何链表之前脑子里会自动出现一条检查链当前的指针分别站在哪下一步要改谁改了之后还能从哪找到原来的后继。这种手感才是第四天真正值钱的东西。