写完了DAY4的反转链表不少同学会觉得链表这块已经拿捏了不就是改改指针指向嘛。结果DAY5第二章链表part02一上来画风直接变了不再是单链表的“直线操作”而是开始玩交叉、闭环、快慢指针这些稍微绕一点的逻辑。这一天的内容放在训练营里其实很有讲究它不是单纯堆题目而是把链表题里几个高频且容易写错的场景集中打包让你一次性把指针操作的手感练出来。这篇文章我就把DAY5涉及的核心题目和一些我自己踩过的坑串一遍给正在跟训练营或者自己刷链表的朋友做个参考。1. DAY5在链表训练中的位置从“会写”到“会设计”1.1 为什么part02选的是这四类题代码随想录的训练节奏通常是把基础操作放在前面比如移除元素、设计链表、反转链表这些属于“给你一个明确目标照着写就能完成”的题。到了part02题目难度和思维深度明显上了一个台阶核心考察的不再是“会不会遍历链表”而是“能不能在指针关系上做设计”。这一part集中出现的高频题大致包括两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II。这四道题看起来各不相关实际上有一条暗线把它们串在一起就是指针的“相对位置”和“步长控制”。两两交换节点考的是在相邻节点之间重新建立连接关系删除倒数第N个节点考的是快慢指针之间保持固定间距链表相交考的是两条链表尾部对齐之后同步走位环形链表II考的是快慢指针在环内相遇之后如何定位入口。你会发现这四道题没有一道是“死记硬背能搞定”的每道题都需要你在纸上先画一遍指针指向再动手写代码。这也是训练营把这一天放在第二章后半段的原因前面的题帮你建立了“链表的基本操作”直觉后面才能上这种组合逻辑。1.2 训练营DAY5的典型打卡节奏按照训练营的安排DAY5通常要求当天完成上述四道题的基础版本并且每道题提交通过LeetCode测试用例再在打卡文档里写下时间复杂度和空间复杂度的分析。有些同学会在这里卡住主要卡点不是语法而是“递归写法”和“迭代写法”的取舍以及“虚拟头结点”到底应该在什么场景用。我的建议是part02的题目一定要优先掌握迭代写法递归可以放在后面理解。原因很简单链表题的递归写法虽然代码短但调用栈的跳转逻辑对初学者来说不够直观一旦指错节点调试成本很高。而虚拟头结点这种技巧在part02里几乎每道题都能用到它是解决边界条件最省心的方式后面也会专门展开。2. 两两交换链表中的节点虚拟头结点在“穿针引线”中的典型应用2.1 为什么直接操作头结点会写出一堆if这道题要求把链表相邻节点成对交换位置比如1-2-3-4变成2-1-4-3。第一次写的时候很多人会尝试直接从头结点开始改结果发现处理头结点和中间节点完全是两套逻辑头结点没有“前一个节点”交换完之后头结点身份还会变于是代码里塞满了if (prev nullptr)这种分支。这里就引出了整个part02第一个核心技巧用虚拟头结点统一头结点和普通节点的处理逻辑。虚拟头结点是一个额外的dummy节点它的next指向原链表头操作完之后返回dummy-next这样头结点就变成了“普通节点”所有节点的交换逻辑都一致不需要写特殊分支。这个思路和前面DAY3、DAY4里移除链表元素、反转链表遇到的问题一模一样。链表题里只要发现“头结点需要特殊判断”第一反应应该是加一个虚拟头结点而不是硬写if。2.2 交换过程里的指针指向顺序两两交换节点的循环里有一个特别容易出错的点交换两个节点需要重新连接三条指针这三条指针的赋值顺序不能乱。我们以下面这段常见的虚拟头结点写法为例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; // 先保存第一个节点 ListNode* tmp1 cur-next-next-next; // 再保存第三个节点 cur-next cur-next-next; // 第一步cur指向第二个节点 cur-next-next tmp; // 第二步第二个节点指向第一个节点 cur-next-next-next tmp1; // 第三步第一个节点指向第三个节点 cur cur-next-next; // cur移动两位进入下一轮 } return dummyHead-next; } };关键在于cur-next-next这个表达式在赋值过程中会被改变所以必须在赋值之前把后面要用到的节点地址保存下来。上面代码里tmp保存的是第一个节点的地址tmp1保存的是第三个节点的地址这两个保存动作必须在第一次赋值之前完成。我在实际写的时候会先在纸上画出三个关键节点和四条边标注哪些边会被改写再去写代码。如果直接上手写十有八九会在第二步和第三步的顺序上翻车因为第二步的cur-next-next已经不是原来那个节点了。2.3 边界条件和循环条件的取舍这段代码的循环条件是cur-next ! nullptr cur-next-next ! nullptr很多初学者会问为什么要同时判断两个因为一次交换需要“当前节点后面还有两个节点”缺少任何一个都无法完成交换。如果链表节点数是奇数最后一个节点落单那它就不参与交换保持原位。我自己的习惯是先判断cur-next是否为空再判断cur-next-next是否为空这个顺序不要颠倒。虽然C里有短路求值先判断前者可以在后者访问空指针之前拦下来但从逻辑清晰度来说把“存在性判断”放在前面也符合阅读习惯。另外这一题的递归写法也值得提一下。递归解法的核心是每次处理一对节点然后递归处理剩余部分代码确实短但对递归栈的理解要求更高。训练营打卡阶段建议先把迭代写法写熟递归等二刷的时候再补不迟。3. 删除链表的倒数第N个节点快慢指针的“步长差”是核心3.1 先数长度再删为什么不是最优解链表相交和删除倒数第N个节点这两道题有一个共同的“笨办法”先遍历一遍链表拿到总长度然后通过计算len - n确定要删除的位置再遍历一遍删除。这个方法当然可行时间复杂度和双指针法一样都是O(n)但有个问题它需要两遍扫描。代码随想录里给的思路更巧妙用两个指针一次遍历解决问题快指针先走n步然后快慢指针一起走快指针走到末尾时慢指针刚好停在倒数第n1个节点的位置。这个思想在链表题里非常常见后面做其他题目也经常复用。这里要特别强调的是快慢指针的核心是“两个指针之间的步长差固定为n”。快指针先走n步相当于是给慢指针一个“后发先至”的缓冲之后两者同步移动差值保持不变这样当快指针到达边界时慢指针的位置就是我们需要的位置。3.2 删除节点时虚拟头结点又派上用场了删除倒数第N个节点的边界情况是如果要删除的是头结点本身直接返回head-next就行但用虚拟头结点可以统一处理。标准写法如下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; // fast再走一步让slow最终停在待删节点的前一个位置 while (fast ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; } };注意这里有几个细节几乎每个初学的人都会问为什么快指针要先走n1步而不是n步因为我们要让slow停在待删节点的前一个节点这样执行slow-next slow-next-next的时候才不需要额外保存待删节点的地址。如果fast只走n步那么fast走到末尾时slow正好落在待删节点上那就还得再写一栏previous指针增加了复杂度。while (n-- fast ! nullptr)这个条件里fast ! nullptr是防御性检查正常情况下不会出现fast为空的情况因为题目保证n是有效的。但刷题嘛防御一下总没坏处。3.3 快慢指针的常见翻车点这个题我见到的错误集中在两处第一处是没有给fast加一步导致slow最终指向待删节点而非前驱节点第二处是在移动fast的时候把fast fast-next写成了循环里的fast 1这是数组时代的习惯没改过来。再说一句题外话链表题里双指针用得多但“快慢指针”这个词在不同题目里含义略有不同。在环形链表II里快慢指针是“速度差”的关系在删除倒数第N个节点里快慢指针是“步长差”的关系。两者区别要分清楚混着理解会让后续做题越来越乱。4. 链表相交与环形链表II指针走位背后的数学推导4.1 链表相交为什么对齐尾部是关键链表相交这道题题目给的链表可能是两条在某个节点开始共用的链表要求找第一个相交节点。最容易想到的方案是双重循环对链表A的每个节点遍历链表B时间复杂度O(mn)在LeetCode上基本跑不过大数据量。好的解法是先计算两条链表的长度差让较长的链表先走差值的步数然后两个指针同步前移第一次相遇的节点就是交点。这里有一个重要的认知如果两条链表相交那么从交点开始到末尾的节点是完全重合的所以相交部分一定位于链表的尾部。基于这个性质我们可以把两条链表“右对齐”来看。长度差就是长链表多出来的头部部分这部分一定不会在相交区域内所以先走掉这部分两个指针就站在了同一起跑线上之后同步走碰到相同节点直接返回。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; // 让curA指向较长链表的头结点 if (lenB lenA) { 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; } };注意这里判断相等用的是curA curB这是指针地址比较不是值比较。面试或者笔试的时候要理解为什么这样判断——因为两条链表的相交本质上是它们指向了同一批节点而不是两个值相同的不同节点。4.2 环形链表II快慢指针相遇后的入口推导环形链表II是part02里公认最难的一道题也是思想性最强的一道。题目要求判断链表是否有环并返回环的入口节点。代码随想录给的是快慢指针解法fast每次走两步slow每次走一步如果两者相遇说明有环然后从相遇点和头结点同时出发两个指针每次各走一步它们相遇的位置就是环的入口。很多同学能背下来结论但不明白为什么最后能相遇在入口节点。这里我试着把推导过程讲清楚一点。假设头结点到环入口的距离为x入口到fast和slow第一次相遇点的距离为y相遇点继续走到入口的距离为z。慢指针走的距离是x y慢指针进入环后走不到一圈就会被追上快指针走的距离是x y n(y z)其中n表示快指针在环里多绕的圈数至少为1。因为fast速度是slow的两倍所以2(x y) x y n(y z)整理得x y n(y z)也就是x n(y z) - y (n - 1)(y z) z这个式子说明从头结点出发的指针走x步到达入口而从相遇点出发的指针走z步到达入口如果多绕几圈再回到入口的路径也符合这个距离。所以用一个指针从头结点出发另一个指针从相遇点出发同步走最后一定在入口相遇。这个推导是环形链表II的核心理解了它才算真正吃透这道题而不只是背结论。4.3 fast走两步slow走一步为什么步长取这个比例一个自然而然的问题是为什么fast走两步slow走一步如果fast走三步、slow走一步行不行从数学上说只要fast速度大于slow两者在环内一定会相遇但步长比例会影响可行性。如果fast走三步、slow走一步fast相对slow的速度是两步在环内追赶时可能出现“跳过”slow的情况虽然最终一般也能相遇但分析起来更复杂代码判断也容易出错。两步对一步是最经典的选择因为它保证了fast相对于slow恰好是一步一步逼近的逻辑最简单推导最干净。另外环形链表还有一个常见错误解法用一个set记录访问过的节点遇到重复节点就说明有环。这个解法在LeetCode上也能过空间复杂度却是O(n)面试时如果说了这个方案通常会追问能不能优化到O(1)。快慢指针就是那个O(1)空间的方案。5. 链表题调试的五个实操技巧5.1 本地搭建可打印的链表环境刷链表题最痛苦的事情是代码在LeetCode上能跑通但一旦报错看不到链表中间过程。我建议花一点时间在本地配置一个可以打印链表结构的小环境。比如在C里写一个printList函数void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout cur-val - ; cur cur-next; } cout null endl; }然后在每个关键步骤之后调用一次printList观察指针是否按照预期移动。这比在LeetCode上print调试要灵活得多也方便构造各种边界用例。5.2 构造边界用例的习惯part02的四道题每道题都有明显的边界场景。两两交换要考虑奇数长度删除倒数第N个要考虑删除头结点链表相交要考虑不相交和交点在头部环形链表要考虑入口就是第一个节点。这些边界用例建议在写代码之前就写在注释里写完代码之后一个用例一个用例地套。我自己刷链表题时有个习惯先跑空链表再跑单节点再跑双节点最后跑长链表。空链表和单节点是最容易踩段错误的地方而这类错误LeetCode只报runtime error不给具体原因调起来很费劲。5.3 防止指针越界和空指针访问链表题90%的bug都是空指针访问。cur-next-next这种表达式编译器不会帮你检查cur本身是不是空指针一旦cur为空程序直接崩溃。所以写链表代码的时候要形成一种肌肉记忆凡是想访问cur-next先确认cur不是nullptr凡是想访问cur-next-next先确认cur-next不是nullptr。这个习惯在写part02的时候特别重要因为虚拟头结点的使用让循环条件变复杂了很容易出现cur-next已经为空但循环体内还要访问cur-next-next的情况。5.4 复杂度分析不要写错链表题的复杂度分析经常被忽略但在面试和笔试里很看重。part02的几道题时间复杂度和空间复杂度如下题目时间复杂度空间复杂度两两交换链表中的节点O(n)O(1)删除链表的倒数第N个节点O(n)O(1)链表相交O(m n)O(1)环形链表IIO(n)O(1)注意链表相交这里m和n分别表示两条链表的长度空间复杂度由于只用了常数额外变量是O(1)而不是O(mn)别因为计算了两个长度就误以为空间也要O(n)。5.5 画图是链表题最重要的“调试工具”我知道很多同学刷题喜欢直接在脑子里模拟指针变化但这真的不是好习惯。链表题最可靠的调试方式就是在纸上画图。画的时候用一个方框代表节点框里写值外面标注地址用箭头表示指针。每执行一步操作就改画一遍箭头。特别是两两交换和环形链表II这两道题画图和不画图的效率差至少三倍。环形链表II的推导过程我第一次看的时候也是一头雾水后来把x、y、z三个距离标在图上设了变量代进去算才真正理解了为什么相遇点和头结点同时走能碰上。6. DAY5之后链表的整体框架该怎么搭建6.1 从part01到part02链表题的方法论地图如果只看part01你会觉得链表题就是“老三样”加虚拟头结点、改指针、返回新的头结点。但到了part02你需要在这套基础之上再叠加一层“双指针思维”。这其实暴露了链表题的一个学习规律基础操作是武器题目的条件是战场而双指针、数学推导这些才是战术。现在回头梳理第二章链表部分的方法论大致是这样一个体系基础操作类移除元素、插入、反转以虚拟头结点为核心练的是指针重连的准确性复杂结构类两两交换、删除倒数第N个以双指针相对位置为核心练的是步长控制拓扑关系类相交、环形以数学推导为核心练的是把几何直觉转成代码的能力。掌握了这个体系之后再遇到新的链表题第一步不是急着写代码而是先判断它属于哪一类再想对应的套路。6.2 哪些常见题可以趁热打铁继续练DAY5做完之后如果需要额外巩固我会推荐几道和part02高度同构的题目重排链表143结合了找中间节点、反转后半段、合并三条子逻辑是part02所有技巧的综合应用旋转链表61本质是快慢指针取模运算的一种变体奇偶链表328考察分组合并和pair swap的思维路径很像分隔链表86需要同时维护两条链和链表相交的“对齐”思想有共通点。这几道题不需要在训练营打卡期间全部完成但二刷或者冲刺面试之前很有必要集中过一遍。它们共同的特点是单看每步都不难难的是把多段逻辑串联起来而这正是part02想训练的能力。6.3 关于打卡节奏的个人建议最后聊一点我自己的感受。训练营的DAY5对很多人来说是一个分水岭原因不是题目本身有多难而是从这一天开始链表题不再是“照着模板敲”的状态它第一次要求你在脑子里建立“指针拓扑图”。如果你在DAY5卡住了这不是能力问题只是缺少画图模拟的过程。给自己准备一叠草稿纸每道题先把图画出来再写代码你会发现很多“想不通”的地方在图上一目了然。代码随想录把链表part02放在这个位置本身就是在传递一个信号数据结构的学习不是背API而是建立模型。链表是最简单的动态数据结构之一它逼着你用“节点指针”的视角去看待数据组织方式。过了这一关后面二叉树、图论里的指针关联和递归结构理解起来都会顺很多。DAY5辛苦是辛苦但这一关值得好好啃。