1. 刷题第四天链表题的“分水岭”在哪里能刷到《代码随想录》day4的多半已经不是第一天那种“今天学了数组、明天看字符串”的节奏了。前三天把数组、哈希表这些基础结构捋了一遍到了链表这一章很多人的感受是从“看得懂题解”变成“自己写不出来”——这是非常正常的信号。day4的内容是链表专题第二天的四道题两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II。这四道题放在一起不是随便凑的它们共同指向了两个核心技能对指针/引用操作的精熟度和对边界条件的敏感性。说句实在话刷链表题最让人挫败的时刻不是“思路想不到”而是“思路明明对代码跑出来全是错”。你画图觉得没问题一写代码就卡在指针指向、空指针判断、循环条件上这四道题几乎把这些坑全部覆盖了一遍。所以day4对你的意义不是多刷四道题而是通过这四道题把链表操作里最容易翻车的地方彻底搞清楚。这篇文章适合三类人一是正在跟代码随想录学习路线的同学配合day4做复盘二是准备面试但链表题总是“会画图不会写码”的朋友三是已经刷过这几题、想看有没有遗漏注意事项的老人。我会按自己的理解把每道题的核心思路、代码细节和踩过的坑都讲一遍尽量让你读完之后能直接复现而不是只能看懂个大概。2. 两两交换链表中的节点结构变形题的思维断点2.1 核心思路把“交换两个节点”看成“重组三节点组”先明确题目给定链表1-2-3-4要求返回2-1-4-3。要求不能修改节点内部值只能操作节点引用。题目本身不难理解难的是链表交换类操作里一个经典的思维断点——当你想交换节点A和节点B时你需要的其实不只是A和B这两个引用还需要它们前一个节点的引用否则交换完之后前面那个节点还指着旧的节点链表就断了。代码随想录给出的解法是用虚拟头节点dummy node这几乎是我见过的所有链表操作题里最值得养成的习惯。你在原链表头前面加一个哨兵节点让dummy-next head然后从dummy开始遍历。这样一来原来的head就变成了普通节点所有对“头节点”的特殊处理都消失了代码统一度直接上升一个档次。具体的操作逻辑是这样的假设当前需要交换的是cur-next和cur-next-next这两个节点也就是cur指向交换前的第一个节点的前置节点。你需要先把cur-next记为A和cur-next-next记为B保存下来然后按顺序调整三条指针cur-next B、B-next A、A-next B-next保存B原来的next。最后把cur移动到A继续下一组。这三步就是“重组三节点组”的完整过程核心在于保证断链之前引用不丢。我见过很多新手连写三步都不行原因不是不懂逻辑而是没意识到C语言里p-next-next这种表达式一旦中间一步改变了指针后面的取值可能已经不是你想象的那个节点了。所以稳妥做法一定是先存引用、再动指针。2.2 循环条件的边界陷阱这道题最容易错的不是交换逻辑本身而是循环条件。很多人会写成while (cur-next ! NULL cur-next-next ! NULL)这个方向是对的但有个细节值得停下来想想为什么不能只判断cur-next ! NULL因为你要交换的是两个节点当前节点之后至少要剩两个节点才存在“两两交换”的可能。如果只剩一个节点它没有配对对象直接不动。这个判断条件保护的就是这种奇数长度的链表。cur初始指向dummy也就是在第一个节点之前所以每轮判断的都是“当前轮次待交换的两个节点是否存在”。有同学会问cur-next ! NULL和cur-next-next ! NULL两个条件的先后顺序有没有讲究有。必须把cur-next ! NULL放前面这是短路运算符的逻辑要求——如果cur-next已经是NULL再访问cur-next-next就是空指针解引用这在C/C里是未定义行为在Java里直接抛空指针异常。顺序反了必崩。还有一个隐藏的误会交换完之后cur应该移动到哪里不是移动到交换后的第二个节点而是移动到交换前的第一个节点也就是A。因为A经过交换后变成了这一组节点的“尾部”下一组待交换的节点就挂在A后面。这个位置很多人会忘记导致同一组节点被反复交换死循环。2.3 实操中的几个注意点我刷这道题时记录过三个容易犯的错很有意思分享出来你可能也会遇到。第一个是保存引用的时机。我看过有人先执行cur-next cur-next-next再去保存原来的后续引用结果原来的第二节点已经丢了后面全靠脑补在写代码。链表题第一原则动手改指针之前先把要丢的节点全部存下来。三组节点交换最多需要保存两到三个引用不要嫌麻烦。第二个是对虚拟头节点的理解偏差。dummy节点不是用来参与交换的它的值无所谓val可以随便给它的存在纯粹是为了让头节点处理逻辑和普通节点一致。我在面试中问过不少人他们知道用dummy却说不清为什么。记住dummy的价值在于消除特殊情况而不是提供一个额外的有效节点。第三个是Java/Python与C的区别。Java和Python里操作的都是对象的引用直接赋值就相当于把引用改指向C里如果用指针就要格外小心指针的二级引用问题。比如Java里ListNode tmp cur.next随后cur.next tmp.next这个tmp持有的引用不会因为原链表改变而失效。但如果你在C里用ListNode* tmp cur-next同样的逻辑也成立只是释放内存时需要额外考虑原节点是否还要用。这些手感的差异只有在实际敲代码时才能体会到。3. 删除链表的倒数第N个节点双指针的经典引入3.1 为什么是“快慢指针”不是“先数一遍”题目要求删除倒数第N个节点也就是从链表末尾往前数N个位置的那个节点。最笨的方法是两遍遍历第一遍数出链表长度L第二遍走到 L-N 的位置把pre-next cur-next删掉。这种解法没问题很多题目也允许但代码随想录这里教的是一遍遍历的双指针法也就是快慢指针思路先让快指针走N步然后快慢指针同步前进当快指针到达末尾时慢指针恰好停留在倒数第N个节点的前一个位置。为什么这个思路成立因为快指针和慢指针之间的距离被固定为N个节点。当快指针指向NULL的那一刻慢指针距离末尾也就差N个位置它正好指向倒数第N个节点的前驱。这里要特别强调“前驱”这两个字——删除操作的核心永远是找到待删节点的前一个节点而不是待删节点本身。你直接指向待删节点再想删除时是没有办法回头改前驱节点的next的因为单向链表没有prev指针。生活化的类比是两个人排队进电梯其中一个人先走了N步然后停下来等另一个人两个人保持N步距离同步走当前面那个人走到队列尽头时后面那个人站的位置就是你要找的位置。这个类比在面试中用很加分说明你真的理解了双指针的物理含义。3.2 快指针先走N步还是先走N1步这是双指针解法里最经典的细节。如果你用“慢指针指向待删节点的前驱”这个目标来倒推答案就很清晰快指针先走N步此时快慢指针间隔为N然后同时移动当快指针到达NULL时慢指针指向倒数第N个节点但慢指针现在指向的是待删节点本身并不是它的前驱这不符合删除需求。所以正确的做法是快指针先走N1步拉开N1的间隔然后同步移动快指针到NULL时慢指针正好在倒数第N个节点的前一个位置。这时候执行slow.next slow.next.next就完成了删除。这个N1的细节是这道题最大的考点很多人在纸上画图都能明白一写代码就忘了加1然后删除的总是倒数第N1个节点。还有一个就是因为用了虚拟头节点形势会稍微变化dummy存在时快指针先走N步然后快慢指针同步走当快指针到达NULL时慢指针指向的是倒数第N个节点的前驱因为dummy相当于给整个链表在前面垫了一个节点所有索引向后偏移了一位。不同参考书里的写法会不一样你需要看明白它有没有用dummy再决定N还是N1。我在实际刷题时更喜欢统一用虚拟头节点N步走的版本因为dummy天然保证了对头节点删除操作的统一处理——如果删的是原链表的第一个节点没有dummy的话你要额外写head head.next这种特殊逻辑有dummy则完全不需要。代码随想录的写法也是基于这个思路。3.3 删除类题目的共同套路做完这道题你会发现删除类链表题是有固定套路的可以总结成三步第一步补一个虚拟头节点把“删除头节点”这个特殊情况消掉。第二步找到前驱节点无论被删的是第几个节点、倒数第几个节点你要操作的永远是pre节点。第三步执行删除也就是pre.next pre.next.next同时记得处理“被删节点没有额外引用时是否需要释放”的问题C/C环境要考虑Java不用管。这个套路适用面非常广包括删除链表中的重复节点、删除指定值的节点、删除有序链表的重复元素等。掌握了这个框架看到删除类的题你不会慌因为你知道核心动作永远不变变的只是“怎么找到那个pre节点”的方式。这就是刷题从“一道一道刷”到“一类一类刷”的转变点。4. 链表相交与环形链表II从“会做”到“会推”4.1 链表相交先对齐尾部再同步走这道题的题设是给定两个单链表的头节点找出两个链表相交的起始节点如果没有相交返回NULL。“相交”指的是节点的引用相同不是值相同。很多人一开始会想用一个哈希集合把第一个链表的所有节点存进去然后遍历第二个链表查重复这个解法可行但没用上链表相交的几何性质多了空间复杂度。更优的思路是双指针齐头并进但在走之前做一件事对齐尾部。具体来说先分别遍历两个链表求出长度lenA和lenB让长链表的指针先走abs(lenA - lenB)步。这一步做完后两个指针到各自链表尾部的距离相等。然后两个指针同步每次走一步每次比较当前节点指针是否相等。如果不相等且都没到NULL就继续走一旦相等说明找到了交点如果一路走完到了NULL都没遇到相等说明两个链表不相交。有一个巧妙的变体可以省去求长度的过程让两个指针分别从链表A和链表B出发同步走一个走到末尾后跳转到另一个链表的头部继续走。这个做法的数学原理是两个指针走过的路径长度最终相同如果链表相交它们必然会在交点相遇。这个变体代码更简洁但对理解程度要求更高如果面试时不确定自己能不能讲清原理求长度的显式做法反而更稳妥。为什么“对齐尾部”有效因为两个相交链表的结构必然是这样的从交点往后它们就是同一条链表相当于一条公共尾巴。两个链表长度不同只可能是因为在交点之前的部分长度不同。长链表先把多余的那一段走掉剩下两段长度相同再同步走交点就像两个跑步的人在跑同一段路一样速度相同、起点对齐必然同时到达同一个点。4.2 环形链表II的数学推导环形链表II是day4的压轴题也是链表题里少数需要完整数学推导的题目。题设是给定一个链表返回链表开始入环的第一个节点如果无环则返回NULL。如果你对题目没有印象想一下这个场景一个链表内部有个圈你从head出发一直走会无限循环在圈里走不出来题目要你找到那个“圈口”。第一步判断有没有环。经典解法是快慢指针快指针每次走两步慢指针每次走一步从一个起点同步出发。如果链表有环快慢指针必然在环内相遇——慢指针进环后快指针已经在环里转了若干圈它总会追上慢指针。这里有个误区要强调“追上”不是“走过”。快指针速度是慢指针的两倍相对于慢指针它的相对速度是每一步多走一个节点所以只要有环必然在有限步内追上同时追上时不会跳过慢指针——因为相对速度是1不存在“跨过”的可能。第二步寻找环的入口。假设从链表头到环入口的距离为x环入口到相遇点的距离为y相遇点到环入口的剩余距离为z。慢指针走过的路程是x y快指针走过的路程是x y n*(yz)n是快指针在环内比慢指针多走的圈数。由于快指针速度是慢指针两倍所以有方程2 * (x y) x y n * (y z)化简得x y n * (y z)进一步得到x n*(yz) - y (n-1)*(yz) z你会注意到yz恰好是环的周长。这个式子的物理含义是从头节点出发走到环入口的距离等于从相遇点出发再走若干圈加上z的距离。这就是经典结论的来源当快慢指针在环内相遇后让慢指针留在相遇点另起一个指针从头节点出发两个指针每次都走一步它们最终会在环入口处相遇。这个推导第一次看确实绕我自己也是花了大半个晚上才彻底想明白。但说实话面试的时候不需要你在一分钟内推出这个公式但你得能把x z (n1)这种最简单情形讲清楚——大多数题目里快慢指针第一次相遇时n1公式退化为x z也就是说从头节点出发的指针和相遇点出发的指针同步走必然在入口碰面。画个图辅助讲会比干背公式更容易让人信服。4.3 对“快慢指针”这一思想本身的思考day4的几道题反复用到了双指针/快慢指针我建议你在做完之后抽十分钟把“快慢指针”这个思想本身做个总结。快慢指针本质上是一种利用速度差来构造空间位置关系的手段它可以在一次遍历里完成看似需要多次遍历才能做到的事。判断链表有无环用的是“速度差追及”删除倒数第N个节点用的是“固定距离偏移”查找链表中点用的是快指针到末尾时慢指针恰好在中点。这些变体本质上都是同一个思想的延展。你把这一个思想吃透比背十道题的解法都管用。说句题外话代码随想录的路线之所以把链表相交和环形链表放进同一天也许就是因为它们在思路上互相呼应链表相交靠的是“对齐”环形链表靠的是“追及”这两个词放在一起正好构成双指针技术的两大场景。理解了这层关系你就不是在做题而是在建立知识网络。5. 代码实现细节与编译踩坑5.1 C实现要点我自己是用C刷的代码随想录下面的代码片段按C风格写但核心逻辑在Java和Python里是等价的。先看两两交换的核心实现ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr cur-next-next ! nullptr) { ListNode* first cur-next; ListNode* second cur-next-next; first-next second-next; cur-next second; second-next first; cur first; } return dummy-next; }注意第三步为何是first-next second-next放在最前面。如果你先执行cur-next second此时first还留在原位置它的next指向second你想再去访问second-next还是没问题的——因为second本身没有被改变。但如果你先执行second-next first那second-next就指向了first原来的后半截链表引用就丢了。所以顺序很有讲究建议按“先保存后续、再改前驱、再调整内部”的顺序来。再看删除倒数第N个节点的核心实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* slow dummy; ListNode* fast dummy; while (n-- 0) { fast fast-next; } while (fast-next ! nullptr) { slow slow-next; fast fast-next; } slow-next slow-next-next; return dummy-next; }这里用dummy的情况下快指针先走n步就够了因为slow起点是dummy相当于已经在head前面一位当fast走到最后一个节点时slow正好在待删节点的前驱位置。这个写法很优雅笔试面试都是加分项。5.2 常见问题排查速查表问题现象可能原因检查方向交换节点后链表断成两截第二步覆盖了后续节点引用检查是否在修改指针前保存了所有被覆盖的引用交换节点后死循环cur移动位置错误确认cur是否移动到第一节点交换后的尾部节点删除倒数第N个却删了倒数第N1个快指针步数偏差明确有没有使用dummy再决定先走N还是N1环形链表判断超时快慢指针起点不一致或步数设置错误确认两个指针都从头节点起步且快指针每次两步空指针访问异常循环条件顺序错误检查cur-next ! nullptr cur-next-next ! nullptr的先后顺序链表相交判断不到交点误用值相等判断节点相交链表相交比的是引用/地址不是val6. 写在最后day4刷完之后你该带走什么如果你打算把代码随想录整个跟完day4给你留下的东西应该不止四道题本身。我觉得有四个习惯是这一天真正值得沉淀下来的。第一个习惯是虚拟头节点的条件反射。看到对链表头有修改、删除或插入操作先想能不能加一个dummy节点。Dummy不是万能的但在大多数题目里能让代码简洁、边界条件统一省下的时间足够你多写一段注释。第二个习惯是画图辅助指针操作。链表题最忌讳纯脑补。我在刷这四道题时每道题都画了至少三张状态图每一步指针变动都在图上标注。这不是浪费时间这是把抽象逻辑具象化的过程。遇到复杂链表题画图十分钟代码可能只要五分钟。第三个习惯是先写循环条件再写循环体。链表题的循环条件是边界敏感点是空指针的高发区。通常来说思考循环时先明确“什么条件下可以进入下一轮”再写内部操作会减少很多崩溃。第四个习惯是把每道题归类到思想下。两两交换的核心是“重组链接结构”删除倒数第N个节点的核心是“双指针构造相对位置”链表相交的核心是“对齐长度”环形链表的核心是“快慢追加速率差”。四个思想扣住以后再遇到新题你不是从零想解法而是从已有的工具库里挑工具。我相信多年以后你可能记不住day4的具体代码实现但你大概率会记得“链表题改结构要先保存引用”“快慢指针可以制造位置关系”“环形链表的入口推导来自路程方程”。这些才是刷题真正的存量资产。最后再分享一个小技巧刷完这四道题之后别急着看下一章先把每道题用另一种语言重新写一遍。如果你用的是C再用Java写一遍你会发现自己对链表操作的底层理解会明显加深。语言换了编译器的脾气变了但链表操作的本质没有变。这种跨语言的比对是刷题过程中最容易忽略却最有价值的复习方式。