跟刷“代码随想录”的朋友到第四天应该正卡在这组链表题上24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。前三天刚把数组、哈希表和链表基础过完第四天突然上了四道中等题不少人会有点慌。但我觉得这四道题其实是刷链表最划算的一天它们分别戳中了四个完全不同的痛点改指针顺序、找目标节点的前驱、判断结构关系、环的数学检测。把这一天吃透后面的链表题基本就是变体了。这篇文章不会复述题解而是把这四道题放在一起拆它们各自的坑在哪为什么要用虚拟头节点快慢指针为什么能解两道完全不同的题以及我实际刷的时候踩过哪些坑。适合刚开始系统刷题、准备面试或者链表基础不扎实想补一补的人。1. 把四道题放在一起到底在练什么1.1 先看清这四道题的共同底牌链表题翻来覆去就几件事遍历、改指针、找节点、判结构。这四道题刚好把链表面试里最核心的几种能力全覆盖了。24题两两交换练的是“在链表中间改指针顺序”。它不考你多复杂的算法就考你手稳不稳。交换两个相邻节点只需要动三个指针但先后顺序一错要么丢节点要么成环要么直接断链。19题删除倒数第N个节点练的是“找到目标节点的前驱”。链表删除永远是删前驱不是删自己这个思维如果没建立起来后面一系列插入删除题都会写得很别扭。它同时还引出了双指针思路快慢指针从这天开始正式登场。02.07链表相交练的是“判断两个链表结构上的关系”。它不要求改链表只要求找交点但很多人一开始会在“值相等”和“节点相等”之间栽跟头。这题表面的陷阱是数据比较真正的考点是引用比较。142环形链表II练的是“用数学推导配合指针操作”。这是四道题里最难的一道因为它不光要你判断有没有环还要你精确找到环的入口。快慢指针在这里不只是“快慢”两个字背后是一次完整的等式推导。四道题由浅入深从动手改指针到动脑做推导放在同一天刷是非常科学的安排。如果只刷其中一两道你练到的只是局部能力四道连在一起才算是把链表的“常规武器”配齐了。1.2 虚拟头节点是链表题的第一把钥匙先回答一个很多新手会问的问题链表操作什么时候需要虚拟头节点答案是当你的操作可能会影响头节点本身的时候必须用。24题交换如果发生在开头那第一个节点会被换到第二个位置head指针指向的对象变了。19题如果删除的是头节点那你直接返回head肯定返回错。这两种场景下虚拟头节点能让代码统一处理所有位置不需要单独为“头节点”写if分支。虚拟头节点dummy的写法很简单new一个节点让dummy.next指向head。操作时所有指针都从dummy开始走最后返回dummy.next。这个技巧几乎成了链表改结构题的默认动作后两道链表相交虽然不涉及删除不需要虚拟头节点但如果你第一天接触它最好养成“操作头节点前先想一下要不要dummy”的条件反射。1.3 双指针在这四道题里的三个变体双指针不是一种固定写法它是一类思路。这四道题里出现了三种变体第一种是快慢不同速。142题fast每次走两步slow每次走一步步差为1。这种变体专门用来处理“环”的问题因为只要存在环速度不同的两个指针早晚会追上。第二种是固定步差。19题fast先走n步然后fast和slow同步走步差永远保持在n。这种变体专门用来“定位倒数第n个位置”因为倒数第n个位置和链表末尾之间的距离是固定的。第三种是同速相遇。02.07题让两个指针分别从两个头节点出发走完自己的链表再走对方的链表。因为两个指针最终走过的总长度相同所以它们必然在交点或null处相遇。这种变体的核心是“消除长度差”。我在刷题时有个体会双指针本身不难难的是判断该用哪种变体。判断标准就一句话——你想找的目标和“末尾”有没有固定距离。有固定距离就用固定步差不确定是否有环就用不同速度两条链表长度不一样就用同速走对方路。题目核心技巧时间复杂度空间复杂度24 两两交换虚拟头节点 三步指针重连O(n)O(1)19 删除倒数第N节点快慢指针固定步差O(n)O(1)02.07 链表相交长度差消除后同步走O(n)O(1)142 环形链表II快慢指针 数学推导O(n)O(1)这张表值得记一下四道题的共同特征就是时间O(n)、空间O(1)都很符合面试官对“链表操作应该原地完成”的预期。2. 拆透LeetCode 24两两交换难点全在指针顺序2.1 先明确题目到底让干什么两两交换的题意很简单1-2-3-4变成2-1-4-3奇数个节点时最后一个节点不动。但这里有个陷阱题目只能交换节点不能交换节点里的值。你可以先投机取巧去把val交换了那样代码很短但完全没练到链表操作面试时这么干基本会被打回。所以刷这道题就是练“改指针”。拿到这道题第一步要做的不是写代码而是画图。纸上画两个节点1和2前面还有一个prev后面还有一个next。交换后prev应该指向22应该指向11应该指向next。这个图一画出来代码顺序自然就有了。2.2 三步重连少一步都不行先说我现在写这道题的标准写法C版本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; second-next first; cur-next second; cur first; } return dummy-next; }我一开始写的时候最容易忽略的一步是first-next second-next。如果不先把second后面的节点保存下来也就是不先把first和后面的节点之间的关系断掉后面second一旦指向first原本second后面的节点就找不到了。链表断裂的根源几乎都是因为“先连了前面的线忘了后面的线”。正确的顺序是先让first指向交换后的下一个节点然后second指向first最后cur指向second。这相当于把原来的两条边拆掉重新连三条边。哪条线先动完全取决于这条线的目标节点是否已经被保存。second-next在交换后会被first接管所以必须先让first先指向它否则它就丢了。写完之后建议用两个用例自测输入[1,2,3,4]输出应该是[2,1,4,3]输入[1,2,3]输出应该是[2,1,3]。第二个用例就是在检查奇数个数时最后一个节点不参与交换是否正确。2.3 这道题最常见的两个翻车点第一个翻车点是while条件写错。cur-next-next如果为空说明后面只有一个节点不够交换了循环要停。所以要同时判断cur-next和cur-next-next顺序也不能反。因为C如果cur-next是空再访问cur-next-next就是空指针解引用直接崩。第二个翻车点是忘记移动cur。每一次交换完cur要移动到当前这一对的第二个节点也就是原来的first。如果忘了移动循环会在同一个位置反复交换。判断方法很简单交换完一个pair之后cur应该指向“下一对待交换节点的前一个位置”虚拟头节点初始就扮演这个角色。我刷这题时还有个小习惯把循环里的三行重连注释成“1.保存后续、2.反转指向、3.接入前驱”这样回头看代码时不用重新推。注意LeetCode 24的约束是节点数在0到100之间所以head为空的情况必须直接返回空节点。while条件里已经包含了这个处理但如果你单独先写if判断记得不要在这时把dummy丢了。3. 拆透LeetCode 19倒数第N个节点抓住“前驱”两个字3.1 删除链表节点永远删的是前驱的next很多人写19题的第一反应是先遍历一遍拿到链表长度L然后从头走到第L-n个位置把它后面的节点干掉。这确实是最容易想到的解法时间复杂度O(n)O(n)O(n)虽然两趟但也能过。如果你实在想不出其他办法先用这个拿到正确性完全没问题。但题目精妙的地方在于它希望你能用双指针只遍历一遍。为什么快慢指针能定位倒数第n个因为倒数第n个节点和“最后一个节点后面那个空位”之间距离刚好是n。如果让fast先走n步然后让slow从虚拟头节点出发两个指针同步走当fast走到链表末尾时slow正好落在待删节点的前一个位置。这句话请读三遍slow落在的是前驱不是目标节点。很多第一次实现这道题的人最后删错了对象就是没有理解“删除操作必须找前驱”。3.2 快慢指针的步差实现我给出标准的C实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* fast head; ListNode* slow dummy; while (n-- 0) { fast fast-next; } while (fast ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy-next; }这里的关键是第二个while用的是fast ! nullptr这会让slow多走一步从dummy走到目标节点的前驱。为什么因为fast先走了n步之后它和slow之间的步差是n。当fast走完整条链表到达null时它一共比slow多走了n步说明slow距离链表末尾也正好是n步。换句话说slow此时指向的就是倒数第n1个节点也就是目标节点的前驱。有一个常见替代写法是fast先走n1步然后第二个while改用fast-next ! nullptr。两种都能写出正确答案但你要清楚自己写的是哪一种不要让两种写法混在一起否则最后slow的位置会差一个节点。我刚练的时候犯过一次特别蠢的错误fast先走n步然后第二个while用fast-next ! nullptr结果删掉了倒数第n1个节点。后来画图才发现n1和n这两种预先步数配的循环条件必须是对应的。3.3 边界条件删头节点怎么办n等于链表长度的用例是这道题必须单独检查的。比如链表[1,2,3]n3要删的是头节点1。按上面的代码走一遍fast先走3步直接走到了null。第二个while进不去slow一直留在dummy。最后执行slow-next slow-next-next等于dummy直接指向原链表第二个节点头节点被删掉了。这正是我们想要的结果虚拟头节点在这里发挥了价值。如果没有dummy想要处理删头节点的情况就得单独写if代码会丑很多。这也是我为什么强调涉及删除头节点可能性的题直接上dummy。注意LeetCode 19保证了n一定是有效值不会出现n大于链表长度的情况。但如果你在项目里写通用工具函数一定要先判断n的合法性否则fast可能先走到null之后循环条件直接崩。4. 拆透面试题 02.07链表相交比较地址不是比较值4.1 这题最容易被迷惑的地方面试题02.07给你两个链表让你找它们相交的起始节点。注意题目说的是“相交”不是“有相同值的节点”。链表相交的本质是从某个节点开始后面的所有节点地址完全相同。两个链表在内存中共享了同一段后续节点。比较节点是否相同应该比较指针地址而不是比较节点里的val。举个例子链表A是1-2-3-4链表B是5-6-3-4。虽然两个链表里都有值为3和4的节点但如果它们的地址不同就不叫相交。这个迷惑性在图上很容易被忽略因为画图时我们习惯把相同值的节点画在同一个位置实际上它们在内存里毫不相关。刷题时判断自己有没有理解错可以看一个细节比较语句是if (pA pB)还是if (pA-val pB-val)。前者是正确思路后者就是完全跑偏。4.2 长度差解法先对齐再同步走解法思路特别直白两个链表长度不一样但交点之后部分的长度一定相同所以先让长链表的指针走“两个链表长度之差”的步数然后两个指针一起走遇到的第一个相同地址就是交点。代码实现ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) return nullptr; int lenA 0, lenB 0; ListNode* pA headA; ListNode* pB headB; while (pA ! nullptr) { lenA; pA pA-next; } while (pB ! nullptr) { lenB; pB pB-next; } pA headA; pB headB; int diff abs(lenA - lenB); if (lenA lenB) { while (diff-- 0) pA pA-next; } else { while (diff-- 0) pB pB-next; } while (pA ! nullptr pB ! nullptr) { if (pA pB) return pA; pA pA-next; pB pB-next; } return nullptr; }既然要先算长度那这道题必然需要两趟遍历第一趟求长度第二趟找交点。空间上只用几个变量非常干净。还有一个更秀的解法不需要算长度让pA走完A再走BpB走完B再走A两个指针走过的总路程相同最终会在交点相遇。我可以给你Python版的几行代码感受一下def getIntersectionNode(headA, headB): pA, pB headA, headB while pA is not pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA这个写法成立的原因是如果两链表相交pA走过的长度是A的非公共部分B的非公共部分公共部分pB也一样。如果不相交pA最终走完AB全长到达nullpB走完BA全长到达null它们同时为null时也满足pA is pB退出循环返回null。这段代码极其简洁但理解它需要先把“长度差解法”彻底搞懂不要一上来直接背。4.3 为什么长度差解法一定收敛有个朋友问过我万一两个链表不相交呢前面长度差解法的第二个while会走到两个指针都变成null退出循环返回null不会死循环。指针移动有终点这是链表链表不像数组null就是天然的哨兵。我自己的经验是这类“结构对比”的题最忌讳空想一定要拿两个具体的链表在纸上走一遍。你就画一个A长4、B长3且不相交的例子手动执行一次长度差解法的每个pA、pB指针移动十步以内就能理解为什么最后会走到null。5. 拆透LeetCode 142环形链表II一步推导胜过十次试错5.1 先判环再找入口142题是四道题里最难的一道难度在于它有两个阶段第一阶段判断有没有环第二阶段找环的入口。第一阶段用快慢指针fast每次走两步slow每次走一步。如果链表有环两个指针最终会相遇如果没环fast会先走到null。第二阶段很反直觉在第一次相遇之后把fast留在相遇点然后让一个新的指针从头节点出发另一个指针从相遇点出发两个指针都是每次走一步。它们下一次相遇的位置就是环的入口。我第一次看到这个解法的时候是完全不信的凭什么第二次相遇就在环入口后来耐着性子把数学推导走了一遍发现这个结论非常严谨。下面给愿意弄懂原理的人讲讲推导如果你只在乎能AC可以直接跳到代码。5.2 从相遇点到入口的距离推导设链表头到环入口的距离为a环入口到第一次相遇点的距离为b相遇点继续走到环入口的距离为c。那么环一圈的长度L等于bc。第一次相遇时slow走过的路程是ab。fast走过的路程是abk*L因为fast一定比slow多走了至少一圈。fast速度是slow的2倍所以路程也是slow的2倍。由此得到等式 2(ab) abkL ab kL a k*L - b (k-1)*L (L-b) (k-1)*L c也就是说从相遇点出发绕环走c步刚好到环入口从头节点出发走a步也到环入口。a和c的差是环的整数倍。所以第二阶段把两个指针的速度都设为每次一步一个从头节点走一个从相遇点走。头节点指针到环入口时走了a步相遇点指针走了a步也就是绕了(k-1)圈外加c步同样到环入口。两个指针就在环入口精确相遇。很多题解会把k直接当作1得到ac的简化结论。严格来说a和c是模L相等不是无条件相等。但代码里不需要你算这个差值算法本身就自动处理了环的圈数问题。5.3 完整实现与环形题通用注意点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) break; } if (fast nullptr || fast-next nullptr) return nullptr; ListNode* p1 head; ListNode* p2 fast; while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; }写这道题有三个特别容易踩的坑。第一个坑是while循环条件里忘了判断fast-next。fast每次走两步如果fast-next已经是null再取fast-next-next就会空指针报错。所以循环条件必须是fast fast-next两个判断都不能少。第二个坑是误以为有环会让快慢指针无限循环。其实不会因为fast相对slow每次只快一步每过一轮两者距离就缩小1如果环周长是m最多m轮就会相遇不存在无限循环。第三个坑是判定“无环”的条件。fast最终会走到null或者fast-next为空这就说明链表无环。这个判断要写在第一次相遇判断之后如果fast提前退出循环那说明没有环直接返回null。另一个值得想清楚的细节是为什么相遇一定发生在慢指针入环后的第一圈内因为fast是slow速度的两倍slow入环时fast已经在环里。假设slow入环后走了x步fast同时走了2x步由于两者相对速度为每轮1步x的取值范围最大也只到环长所以fast必然在slow绕环一圈之前追上它。这个结论可以帮助你放心使用第二阶段算法不用担心slow已经绕了多圈导致推导失效。6. 刷完这四道题我总结的排查清单6.1 链表题通用的三张检查表刷完这四道题之后我开始形成一个习惯不管是自己写新题还是帮别人debug都按三张表过一遍。第一张是空指针检查表。涉及cur-next-next的写法必须确认cur-next非空。涉及fast每次走两步必须确认fast和fast-next非空。永远记住链表的尽头是null而null身上没有next。第二张是边界条件检查表。每次写完链表题至少自测这几个输入空链表、只有一个节点、两个节点、头节点被删、奇数个节点、偶数个节点。别嫌多很多隐藏bug就是在这几个用例里暴露的。第三张是指针丢失检查表。问自己三个问题我有没有在断开某个next之前把那个节点保存下来我返回的是不是虚拟头节点的next循环结束之后我有没有把游标指针移动到正确位置检查项常见症状对照题目空指针运行期Segmentation Fault24、142循环条件错误少交换一组或死循环24、19指针丢失链表后半段不见了24、02.07返回错误头节点头节点被删后返回旧head19比较了值而非地址相交题得到错误答案02.076.2 现场调试用的土办法如果你现在还不太会用IDE的断点调试链表我推荐一个土办法在while循环里打印当前节点的值以及下一步要访问的节点是否存在。比如24题就可以在每次交换前打印cur-next-val和cur-next-next-val很快就能看出哪一步的指针接错了。还有一个更土但更高效的方法用纸笔画“节点方框”把每个指针想象成一个箭头。没画图之前觉得指针很抽象画完图之后会发现链表题全部是“把箭头从A挪到B”的机械操作。6.3 关于“看题解才能写出来”这件事刷这四道题的时候你很可能需要看题解。我见过太多人因为“看了答案才AC”而自我怀疑。但链表的题就是这样第一次见就是想不到这很正常。真正重要的是看完题解之后能不能脱稿复现以及第二天能不能不查资料再写一遍。我自己的方法是看完题解后合上代码自己在纸上把例子走一遍然后重新打开编辑器手打代码。能写出来且通过所有边界用例才算这题真正过了一遍。第二天再刷一遍这四道题如果能三十分钟内全部AC那这组的核心技巧基本就是你的了。我个人在实际操作中的一个体会是这四道题适合当作一组“链表基本功套餐”反复刷不要AC一次就再也不看了。一周后回来复刷你会发现第一遍觉得很难的142题第二遍已经能自己推出推导过程了。到那时候你才算真的不是“背题解”而是理解了指针是怎么工作的。最后再分享一个小技巧刷链表题之前先默写三行代码——创建一个虚拟头节点、遍历链表、删除某个节点的后继。这三行是绝大多数链表操作题的“地基”。地基稳了24、19、02.07、142的套路再往上一套会顺手很多。链表题难吗真不难难的是每次都不把基础动作练顺就开始冲难题。