开头代码随想录训练营进行到第四天今天的四道链表题可以说是链表面试中的“钉子户”——24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。四道题难度从简单到中等每一道都对应着一个高频考点虚拟头节点、双指针、哈希表、数学推导。如果你之前刷链表题只是“看题解背代码”今天这组题会逼着你把链表操作的基本功真正夯实。这四道题解决了什么问题呢简单说它们分别训练了你对链表结构的三个核心能力第一对指针指向变化的掌控力两两交换第二用双指针把时间复杂度优化到O(n)的思维能力倒数第N个节点、链表相交第三把“快慢指针数学关系”落地到代码里的能力环形链表II。无论你是刚准备面试的校招生还是想巩固数据结构的职场人这四道题都值得反复做尤其是第二遍第三遍时你会发现自己对“指针”的理解完全不同了。这篇文章我把每道题的思路拆解、代码实现、易错点以及我实际跑代码时踩过的坑全部写出来部分代码属于训练营中的常见解法我也会做一些基于个人实践的补充说明。希望能帮正在刷题的你少走弯路。1. 两两交换链表中的节点LeetCode 241.1 题目理解与核心思路这道题的要求是给定一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你不能只是单纯的改变节点内部的值而是需要实际的节点交换。很多第一次刷这道题的同学容易有个误区以为交换节点值就能交差。题目明确禁止了而且从面试角度来说面试官也绝对不会满足于“交换val”这种取巧方案因为交换节点本身才能真正考察你对链表指针操作的理解。核心思路其实很朴素把链表按两个节点一组切开每一组内部交换顺序。但因为链表不像数组可以随机访问你在交换时必须同时知道“前一个节点”和“后面两个节点”不然一改指针原来的链表就断了。这里就需要用到链表中极其重要的工具——虚拟头节点dummy head。原因很简单头节点没有前驱节点如果直接交换前两个节点头指针本身就要更新而用虚拟头节点后头节点的“前驱”就变成了dummy所有节点都能用统一逻辑处理不用单独为头节点写if判断。1.2 迭代实现与虚拟头节点我给出我实际在本地运行的代码加了详细注释struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0, head); // 虚拟头节点 ListNode* cur dummyHead; // cur指向待交换的前一个节点 // 要交换cur后面的两个节点cur-next和cur-next-next 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; // 移动cur到下一组的前驱即交换后的第二个节点原first } return dummyHead-next; }这里最关键的三个指针操作顺序很多人容易写错。我建议你按“先保存后节点再断开重连”的思路来记first-next second-next让第一个节点先跳过第二个节点指向后面的节点。这样即使后面指针全乱了链表也不会丢。second-next first让第二个节点反过来指向第一个节点。cur-next second让前驱节点指向新的头部即原来的second。这三步顺序不能乱。如果你先执行第二步那么second-next指向first后第一步执行时first-next还在但此时second-next保存的是first而first-next就是原来的second你会发现指针交叉了。实际操作中最好每一步都在纸上画出来别凭感觉写。循环条件为什么是cur-next ! nullptr cur-next-next ! nullptr因为cur始终是“待交换组前的一个节点”如果cur后面没有节点或者只有一个节点那就没有可交换的了。这个条件我一开始写成cur-next cur-next-next后面测试空链表和单节点链表才发现必须要判断cur-next不为空否则cur-next-next会解引用空指针。这是新手最容易踩的坑之一。1.3 递归写法和空间复杂度分析除了迭代递归也能解决。递归的写法比较简洁但初学者更容易绕晕。核心思路是先交换head和head-next两个节点然后递归处理后面的链表。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; }递归的终止条件是当前没有节点或只有一个节点。每一层只考虑当前两个节点的交换后面的交给递归。这里需要注意递归会使用系统栈链表较长时比如几万甚至几十万节点可能会造成栈溢出迭代法空间复杂度是O(1)递归空间复杂度是O(n)。在面试中我一般先写迭代如果面试官要求简洁再补充递归版本。我实际测试过这道题在LeetCode上迭代和递归的运行时间几乎没有明显差距但迭代法在内存管理上更友好毕竟递归调用栈是要消耗资源的。如果要求原地修改且不能用额外空间优先迭代。1.4 常见错误汇总错误一没有使用虚拟头节点导致交换前两个节点后返回的head还是原来的头节点已经是第二个节点了。解决办法用dummyHead最后返回dummyHead-next。错误二循环内忘记移动cur。如果不在最后执行cur firstwhile会无限循环因为cur-next始终是原来的second条件一直成立。这个问题我debug了十几分钟后来打印链表节点才发现cur根本没动。错误三只交换了值。用swap(first-val, second-val)虽然通过了但题目不允许而且面子上也过不去。2. 删除链表的倒数第N个节点LeetCode 192.1 题目理解与双指针思路题目要求给定一个链表删除链表的倒数第n个节点并返回头节点。进阶要求是一次遍历完成。常规思路是两次遍历第一次算出链表长度L第二次找到L-n的位置删除。但一次遍历更优雅也就是“双指针法”。这个思路的原理是让快指针先走n步然后快慢指针同时走。当快指针走到链表末尾时慢指针正好指向倒数第n个节点的前一个节点然后直接跳过要删除的节点即可。这个思路有点像你跑步追人你让朋友先跑n米然后你们两个同速跑朋友到终点时你离终点正好是n米。在这个题目里慢指针所在位置就是从终点倒数第n个位置往前一个节点。为什么要“前一个节点”因为单链表删除一个节点必须知道它前一个节点的指针。所以慢指针最终要停在待删除节点的前驱。2.2 虚拟头节点加双指针的完整实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0, head); ListNode* fast dummyHead; ListNode* slow dummyHead; // 快指针先走n1步这样slow最后指向待删节点的前驱 while (n-- fast ! nullptr) { fast fast-next; } // 因为题目保证n有效这里其实fast一定不为空但严谨起见要判断 // 快慢指针同时走 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // 此时slow-next就是倒数第n个节点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 释放内存在LeetCode上可以不管但本地我们养成习惯 return dummyHead-next; }这里有个非常关键的点快指针先走几步很多同学认为是n步但我实际推导后发现应该是n1步。为什么假设链表长度为L快指针先走n步后快指针离链表末尾还有L-n步。然后两指针同步走当快指针到达末尾即快指针的next为空时慢指针走了L-n步慢指针此时的位置是从头开始的第n步因为起点一样。我们算一下慢指针从dummyHead出发走L-n步后它在第L-n个位置其next指向第L-n1个节点。倒数第n个节点是正数第L-n1个节点。也就是说慢指针正好指向待删节点的前驱。那么快指针只需要走n步即可。但为什么上面的代码是n1因为while循环的终止条件是fast-next ! nullptr而不是fast ! nullptr。如果快指针先走n步然后当fast走到最后一个节点非null时fast-next为空循环停止。此时快指针总共走了L步从dummyHead到最后一个节点需要L步。慢指针走了L步不对。我们重新推导dummyHead是虚拟头节点实际链表长度L。快指针先走n步到达链表第n个节点从1计数。然后快慢同步走每走一步快指针距离末尾就近一步。当快指针到达最后一个节点时从此刻位置到末尾还有1步即next为空时需要停止。整个过程快指针走了L-n步其实这里容易混淆。我建议直接记住一个结论如果循环条件是fast-next ! nullptr那么快指针要预先走n1步如果循环条件是fast ! nullptr那预先走n步但那样慢指针会指向待删节点本身删除不方便。为了避免混乱我自己的记忆方法是让快指针指向待删除节点的前驱位置。也就是说快指针先走n1步此时fast指向从头部数第n1个节点由于dummyHead的存在实际相当于链表第n个位置的下一个。后面同步移动当fast到达最后一个节点时slow正好指向倒数第n1个节点即待删节点的前驱。另外还有一个小技巧如果不用虚拟头节点当n等于链表长度时要删除的正好是头节点此时slow在dummyHead处slow-next就是头节点删除没问题如果不加dummy代码要单独判断所以虚拟头节点真的香。2.3 边界情况与内存释放细节这道题的边界情况主要是n等于链表长度以及链表只有一个节点。使用dummyHead后其实都统一了。我遇到过的问题是本地测试时删除节点后没有释放内存。虽然LeetCode不检查内存泄漏但在实际工程里或者在面试手撕代码时面试官可能会问“你怎么处理被删除节点的内存”。用C尤其要注意删除后要把指针置为nullptr避免悬空指针。我在本地环境用delete toDelete;来释放但如果toDelete后来还被其他指针引用就会出现问题。安全起见释放后不再使用它即可。这道题还有一种写法用栈或数组记录节点位置空间复杂度O(n)。但双指针法是标准答案面试中一定要能现场写出来。3. 链表相交面试题 02.073.1 题目理解与本质这道题也是常考的原题给定两个单链表找出它们的第一个公共节点。注意题目中的“相交”不是指节点值相同而是指两个链表从某个节点开始后面的节点指针完全重合。也就是说两个链表共用一段节点。很多人第一次看到会有疑惑“两个链表怎么可能相交呢”因为在单链表中每个节点只有一个next指针所以一旦两个链表相交从交点开始它们就是同一条链表了。形状上两个链表是“Y”字形而不是“X”字形。链表相交的物理意义其实是一个节点既被链表A的某个节点指向也被链表B的某个节点指向。这道题的暴力做法是遍历链表A的每个节点再遍历链表B看指针是否相同时间复杂度O(m*n)。面试官肯定不满意。高效做法有两种哈希表法和双指针对齐法。训练营主要推荐双指针。3.2 对齐末端法的工作原理双指针解法核心是既然从交点到最后是共用的那么两个链表不同的部分只可能在交点之前。如果把两个链表“末端对齐”——也就是让较长的链表先走差值步然后两个指针同步走第一个相遇的节点就是交点。用例子说明链表A长5个节点链表B长3个节点如果它们相交交点不可能在A的前3个节点之外和B的整个部分其实交点后的长度是相同的所以交点一定离两个链表末端有相同的距离。因此链表A比链表B多出的两个节点肯定在交点之前。让A的指针先走2步然后两个指针一步一步走当它们指向同一个节点时就是交点。如果走到末尾还没有相交返回null。这里需要注意链表相交是“指针相同”而非“值相同”。所以我写代码时判断条件一定用节点指针本身进行比较不要用val。3.3 实现代码与常见疑问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 (lenA lenB) { swap(lenA, lenB); swap(curA, curB); } int gap lenA - lenB; // 长链表先走gap步 while (gap--) { curA curA-next; } // 同步走 while (curA ! nullptr curB ! nullptr) { if (curA curB) return curA; curA curA-next; curB curB-next; } return nullptr; }这个代码如果两个链表长度不同通过swap让curA始终指向较长的链表。这是一种省事的写法但稍微有点绕。如果你不想用swap也可以写if分支。常见疑问一如果两个链表不相交会不会死循环不会因为同步走时它们最终都会到达null循环条件curA ! nullptr curB ! nullptr会终止最后返回null。常见疑问二为什么不能用“值相等”判断因为不同链表中值相同的节点可能很多而且题目要求是“同一个节点”也就是内存地址相同。只有指针比较才靠谱。常见疑问三能不能用哈希表能先把链表A的所有节点指针放入哈希表再遍历链表B第一个在哈希表中出现的节点就是交点。时间复杂度O(mn)空间复杂度O(m)。面试时可以提一下但双指针法空间O(1)更优。3.4 我踩过的坑第一次写这道题时我只计算了长度但没有处理“一个链表为空”的情况导致求gap时出现负数或未定义行为。后来加上长度判断和swap后就稳定了。另外测试时我喜欢自己构造两个相交链表结构上要注意两个链表必须共享后续节点所以不能简单地创建两个独立链表然后把它们的尾部改成相同值的节点而要让它们实际指向同一块内存。比如// 构造相交 ListNode* common new ListNode(8); common-next new ListNode(4); ListNode* headA new ListNode(1); headA-next new ListNode(3); headA-next-next common; ListNode* headB new ListNode(2); headB-next common;如果不注意这个很容易造出错误用例导致测试结果不准。4. 环形链表IILeetCode 1424.1 涉及的知识点和快慢指针思路这道题是链表题里综合难度较高的一题要解决两个问题第一判断链表是否有环第二如果有环找出环的入口节点。在力扣上这题的输入会比较特殊因为题目给了pos表示环入口位置但我们做题时使用的是传入的head不能直接知道入口必须通过快慢指针来推导。先解决第一问。常规做法是快慢指针慢指针每次走一步快指针每次走两步。如果链表无环快指针会先到达null如果有环快指针会进入环内一直绕圈最终会追上慢指针。这个判断方法很好理解就像两个人在操场上跑步一个快一个慢快的人迟早会套圈追上慢的人。但为什么快指针每次是“两步”而不是三步、四步其实三步也可以追上但两步是效率与判定的平衡。更关键的是两步的设定让后续推导环入口变得简单。如果一步快慢指针速度一样永不追上如果三步算法也正确但追击过程中可能“跳过”慢指针需要更仔细的边界处理而且从环入口推导的数学关系会变复杂。4.2 数学推导相遇点、头节点与入口的关系这是本题最核心的部分。假设从头节点到环入口的距离是x节点数环入口到快慢指针第一次相遇点的距离是y相遇点继续走到环入口的距离是z。那么环的周长是yz。慢指针走过的距离x y这里要说明一点慢指针进环后走的第一圈内一定被快指针追上不会走第二圈因为快指针相对慢指针每次多走一步绕环一圈就能追上。快指针走过的距离设入环前走了x入环后在环内走了若干圈设圈数为n从入口走了y到达相遇点所以快指针总距离是x n*(yz) y。由于快指针速度是慢指针的两倍相同时间内快指针距离是慢指针的两倍所以2*(x y) x n*(yz) y化简得到x y n*(yz)再变形x n*(yz) - y (n-1)*(yz) z当n1时x z。这意味着从头节点到环入口的距离等于从相遇点继续走到环入口的距离。这是一个非常重要的结论。即使n大于1公式中(n-1)*(yz)是环周长的整数倍说明从相遇点走z到达入口后再绕几圈也仍然在入口。所以结论依然成立如果一个指针从头节点出发另一个指针从相遇点出发每次都走一步它们必然会在环入口处相遇。因此整个算法的流程是快慢指针从头节点出发快指针每次两步慢指针每次一步。如果快指针遇到null说明无环返回null。第一次相遇时让一个指针从头节点重新出发另一个指针在原地两个指针每次都走一步。再次相遇的位置就是环入口。4.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) { // 有环找入口 ListNode* index1 head; ListNode* index2 fast; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; }这段代码在LeetCode上测试是没问题的。但我在本地测试时需要构造带环链表这里有个大坑如果用普通构造方式很容易构造出无效环导致程序死循环。比如ListNode* head new ListNode(3); ListNode* node2 new ListNode(2); ListNode* node0 new ListNode(0); ListNode* node4 new ListNode(-4); head-next node2; node2-next node0; node0-next node4; node4-next node2; // 环入口是node2注意node4-next指向node2而不是node2-next。如果指向node0那这三个节点会形成一个更小的环node2、node0、node4都不在环外入口就不一样了。另一个坑在第二段我的代码用ListNode* index1 head; ListNode* index2 fast;这里fast就是相遇点。很多同学写成index2 slow其实一样的因为相遇时slow和fast指向同一个节点。但要确保不是null。在while循环结束后index1和index2相等返回。4.4 为什么n1就够以及快指针的步长有些同学会问如果快指针在环内走了不止一圈公式里n1那x (n-1)*(yz)z怎么看其实代码不用区分n是多少。因为从相遇点出发走z步到入口若走(n-1)*(yz)z中间绕了n-1圈最后还是回到入口。所以双指针从头和相遇点同时走每次都一步它们会在入口相遇但要注意从头出发的指针走了x步到达入口从相遇点出发的指针走了z步也到达入口但由于yz0它们两个必须同时到达入口我们来验证从头指针到达入口时走了x步由公式x (n-1)*(yz)z也就是说从相遇点出发的指针需要走同样多的步数才能和从头指针相遇吗实际上代码中while循环直到两个指针相遇才停。从头出发的指针走x步到达入口时从相遇点出发的指针也走了x步由于xz整圈数所以它此时也在入口。因此它们会在入口相遇。如果环很大x很大它们也会继续走直到同时到达入口。这一步推导很关键我建议你动手画一个带环链表把x、y、z标出来再用一个短的环比如3个节点验证一下会特别清晰。快指针步长为什么不能是1因为快慢速度一样永远追不上。那步长3可不可以判断环没问题但找入口推导就会变成3*(xy)的等式同样能推出类似结论但可能涉及倍数变化需要快指针多绕圈。但两步是代码随想录和大多数面试标准直接记住两步就好。4.5 常见失败点和测试技巧这道题最常见的失败原因是忘记处理fast-next为空的情况。如果链表是线性无环fast会走到null如果只判断fast ! nullptr那么fast fast-next-next时如果fast-next本身就是null就会解引用空指针。所以循环条件必须是fast ! nullptr fast-next ! nullptr。还有一个好用的测试技巧当你想验证算法是否找到正确入口时可以让节点结构里加一个val标记打印节点的val。但不要只通过val来判断入口因为可能有重复值。5. 今天的题目总结与实用技巧5.1 四道题的核心共通点今天这四道题表面上是四道题实际上是两个核心技巧的反复应用。第一个技巧是虚拟头节点。在第24题和第19题里虚拟头节点让我们免去了对头节点特殊情况的讨论。删除头节点、交换前两个节点这些问题在有了dummyHead后都变得和其他节点一样。实际上凡是涉及“第一个节点可能被修改或删除”的链表题无脑加虚拟头节点几乎总是对的。第二个技巧是双指针。第19题用了快慢指针的差速第02.07题用了“先走差值”的双指针第142题用了快慢指针判环加相遇。双指针在链表里的三兄弟前后指针倒数第N个、并行指针相交、快慢差速指针环。把这三种理解透很多链表题都能迎刃而解。另外第24题的指针重连三步本质上也是对链表插入和删除操作的变形。我建议你在刷题时每一个操作都在草稿纸上画出指针变化画着画着就懂了。5.2 我个人的刷题节奏和debug经验今天这四道题我实际用时大概三个小时。前两题比较顺利第三题在构造测试用例上花了不少时间第四题在推导公式上卡了一会儿。如果你也卡住我建议你换一种方式不看题解自己先画图推导再对照代码。尤其是环形链表II如果你只是背代码过两天一定会忘。必须把x (n-1)*(yz)z这个式子亲手推导一遍。debug时链表题的输出结果可以用一个辅助函数打印链表void printList(ListNode* head, int count 20) { ListNode* cur head; while (cur ! nullptr count--) { cout cur-val - ; cur cur-next; } cout null endl; }注意对于有环链表这个打印函数会无限循环所以要加一个count限制。我在本地测试环形链表时就遇到过程序跑完不结束的情况后来加了count才发现环构造对了只是打印到环里出不来。这是正常的打印有环链表一定要限制次数。5.3 再分享一个用C写链表题的经验C写链表题最烦的就是内存管理。LeetCode上不需要释放内存但本地测试时如果不释放内存泄漏较多。养成好习惯的话每个new出来的节点都要对应delete。不过链表的delete要小心顺序先保存下一个节点再删除当前节点。尤其在做删除节点类题目时删除被删除节点后不要再去访问它的next。另外现代C可以多用智能指针但LeetCode默认是裸指针面试手撕也是裸指针所以训练还是以裸指针为主。如果你用Python刷题因为Python有自动垃圾回收不需要关心这些但也要知道指针的引用方式。最后想说的是链表题刷多了你会发现它们不仅仅是“数据结构题”更是在训练你一种思维在操作一个只有前驱和后续的世界里你怎么在只能向后走的约束下精确地找到目标位置。当你把今天这四道题吃透后面再遇到LRU缓存、合并K个链表等更复杂的题时你会感谢今天的积累。第四天还只是一个开始坚持住链表这座山翻过去后后面就是一马平川了。 
长河君 · 2026/10/14 2:12:29 · 阅读 1.2k 链表面试重头戏：虚拟头节点与双指针实战精讲
开头代码随想录训练营进行到第四天今天的四道链表题可以说是链表面试中的“钉子户”——24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。四道题难度从简单到中等每一道都对应着一个高频考点虚拟头节点、双指针、哈希表、数学推导。如果你之前刷链表题只是“看题解背代码”今天这组题会逼着你把链表操作的基本功真正夯实。这四道题解决了什么问题呢简单说它们分别训练了你对链表结构的三个核心能力第一对指针指向变化的掌控力两两交换第二用双指针把时间复杂度优化到O(n)的思维能力倒数第N个节点、链表相交第三把“快慢指针数学关系”落地到代码里的能力环形链表II。无论你是刚准备面试的校招生还是想巩固数据结构的职场人这四道题都值得反复做尤其是第二遍第三遍时你会发现自己对“指针”的理解完全不同了。这篇文章我把每道题的思路拆解、代码实现、易错点以及我实际跑代码时踩过的坑全部写出来部分代码属于训练营中的常见解法我也会做一些基于个人实践的补充说明。希望能帮正在刷题的你少走弯路。1. 两两交换链表中的节点LeetCode 241.1 题目理解与核心思路这道题的要求是给定一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你不能只是单纯的改变节点内部的值而是需要实际的节点交换。很多第一次刷这道题的同学容易有个误区以为交换节点值就能交差。题目明确禁止了而且从面试角度来说面试官也绝对不会满足于“交换val”这种取巧方案因为交换节点本身才能真正考察你对链表指针操作的理解。核心思路其实很朴素把链表按两个节点一组切开每一组内部交换顺序。但因为链表不像数组可以随机访问你在交换时必须同时知道“前一个节点”和“后面两个节点”不然一改指针原来的链表就断了。这里就需要用到链表中极其重要的工具——虚拟头节点dummy head。原因很简单头节点没有前驱节点如果直接交换前两个节点头指针本身就要更新而用虚拟头节点后头节点的“前驱”就变成了dummy所有节点都能用统一逻辑处理不用单独为头节点写if判断。1.2 迭代实现与虚拟头节点我给出我实际在本地运行的代码加了详细注释struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0, head); // 虚拟头节点 ListNode* cur dummyHead; // cur指向待交换的前一个节点 // 要交换cur后面的两个节点cur-next和cur-next-next 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; // 移动cur到下一组的前驱即交换后的第二个节点原first } return dummyHead-next; }这里最关键的三个指针操作顺序很多人容易写错。我建议你按“先保存后节点再断开重连”的思路来记first-next second-next让第一个节点先跳过第二个节点指向后面的节点。这样即使后面指针全乱了链表也不会丢。second-next first让第二个节点反过来指向第一个节点。cur-next second让前驱节点指向新的头部即原来的second。这三步顺序不能乱。如果你先执行第二步那么second-next指向first后第一步执行时first-next还在但此时second-next保存的是first而first-next就是原来的second你会发现指针交叉了。实际操作中最好每一步都在纸上画出来别凭感觉写。循环条件为什么是cur-next ! nullptr cur-next-next ! nullptr因为cur始终是“待交换组前的一个节点”如果cur后面没有节点或者只有一个节点那就没有可交换的了。这个条件我一开始写成cur-next cur-next-next后面测试空链表和单节点链表才发现必须要判断cur-next不为空否则cur-next-next会解引用空指针。这是新手最容易踩的坑之一。1.3 递归写法和空间复杂度分析除了迭代递归也能解决。递归的写法比较简洁但初学者更容易绕晕。核心思路是先交换head和head-next两个节点然后递归处理后面的链表。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; }递归的终止条件是当前没有节点或只有一个节点。每一层只考虑当前两个节点的交换后面的交给递归。这里需要注意递归会使用系统栈链表较长时比如几万甚至几十万节点可能会造成栈溢出迭代法空间复杂度是O(1)递归空间复杂度是O(n)。在面试中我一般先写迭代如果面试官要求简洁再补充递归版本。我实际测试过这道题在LeetCode上迭代和递归的运行时间几乎没有明显差距但迭代法在内存管理上更友好毕竟递归调用栈是要消耗资源的。如果要求原地修改且不能用额外空间优先迭代。1.4 常见错误汇总错误一没有使用虚拟头节点导致交换前两个节点后返回的head还是原来的头节点已经是第二个节点了。解决办法用dummyHead最后返回dummyHead-next。错误二循环内忘记移动cur。如果不在最后执行cur firstwhile会无限循环因为cur-next始终是原来的second条件一直成立。这个问题我debug了十几分钟后来打印链表节点才发现cur根本没动。错误三只交换了值。用swap(first-val, second-val)虽然通过了但题目不允许而且面子上也过不去。2. 删除链表的倒数第N个节点LeetCode 192.1 题目理解与双指针思路题目要求给定一个链表删除链表的倒数第n个节点并返回头节点。进阶要求是一次遍历完成。常规思路是两次遍历第一次算出链表长度L第二次找到L-n的位置删除。但一次遍历更优雅也就是“双指针法”。这个思路的原理是让快指针先走n步然后快慢指针同时走。当快指针走到链表末尾时慢指针正好指向倒数第n个节点的前一个节点然后直接跳过要删除的节点即可。这个思路有点像你跑步追人你让朋友先跑n米然后你们两个同速跑朋友到终点时你离终点正好是n米。在这个题目里慢指针所在位置就是从终点倒数第n个位置往前一个节点。为什么要“前一个节点”因为单链表删除一个节点必须知道它前一个节点的指针。所以慢指针最终要停在待删除节点的前驱。2.2 虚拟头节点加双指针的完整实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0, head); ListNode* fast dummyHead; ListNode* slow dummyHead; // 快指针先走n1步这样slow最后指向待删节点的前驱 while (n-- fast ! nullptr) { fast fast-next; } // 因为题目保证n有效这里其实fast一定不为空但严谨起见要判断 // 快慢指针同时走 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // 此时slow-next就是倒数第n个节点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 释放内存在LeetCode上可以不管但本地我们养成习惯 return dummyHead-next; }这里有个非常关键的点快指针先走几步很多同学认为是n步但我实际推导后发现应该是n1步。为什么假设链表长度为L快指针先走n步后快指针离链表末尾还有L-n步。然后两指针同步走当快指针到达末尾即快指针的next为空时慢指针走了L-n步慢指针此时的位置是从头开始的第n步因为起点一样。我们算一下慢指针从dummyHead出发走L-n步后它在第L-n个位置其next指向第L-n1个节点。倒数第n个节点是正数第L-n1个节点。也就是说慢指针正好指向待删节点的前驱。那么快指针只需要走n步即可。但为什么上面的代码是n1因为while循环的终止条件是fast-next ! nullptr而不是fast ! nullptr。如果快指针先走n步然后当fast走到最后一个节点非null时fast-next为空循环停止。此时快指针总共走了L步从dummyHead到最后一个节点需要L步。慢指针走了L步不对。我们重新推导dummyHead是虚拟头节点实际链表长度L。快指针先走n步到达链表第n个节点从1计数。然后快慢同步走每走一步快指针距离末尾就近一步。当快指针到达最后一个节点时从此刻位置到末尾还有1步即next为空时需要停止。整个过程快指针走了L-n步其实这里容易混淆。我建议直接记住一个结论如果循环条件是fast-next ! nullptr那么快指针要预先走n1步如果循环条件是fast ! nullptr那预先走n步但那样慢指针会指向待删节点本身删除不方便。为了避免混乱我自己的记忆方法是让快指针指向待删除节点的前驱位置。也就是说快指针先走n1步此时fast指向从头部数第n1个节点由于dummyHead的存在实际相当于链表第n个位置的下一个。后面同步移动当fast到达最后一个节点时slow正好指向倒数第n1个节点即待删节点的前驱。另外还有一个小技巧如果不用虚拟头节点当n等于链表长度时要删除的正好是头节点此时slow在dummyHead处slow-next就是头节点删除没问题如果不加dummy代码要单独判断所以虚拟头节点真的香。2.3 边界情况与内存释放细节这道题的边界情况主要是n等于链表长度以及链表只有一个节点。使用dummyHead后其实都统一了。我遇到过的问题是本地测试时删除节点后没有释放内存。虽然LeetCode不检查内存泄漏但在实际工程里或者在面试手撕代码时面试官可能会问“你怎么处理被删除节点的内存”。用C尤其要注意删除后要把指针置为nullptr避免悬空指针。我在本地环境用delete toDelete;来释放但如果toDelete后来还被其他指针引用就会出现问题。安全起见释放后不再使用它即可。这道题还有一种写法用栈或数组记录节点位置空间复杂度O(n)。但双指针法是标准答案面试中一定要能现场写出来。3. 链表相交面试题 02.073.1 题目理解与本质这道题也是常考的原题给定两个单链表找出它们的第一个公共节点。注意题目中的“相交”不是指节点值相同而是指两个链表从某个节点开始后面的节点指针完全重合。也就是说两个链表共用一段节点。很多人第一次看到会有疑惑“两个链表怎么可能相交呢”因为在单链表中每个节点只有一个next指针所以一旦两个链表相交从交点开始它们就是同一条链表了。形状上两个链表是“Y”字形而不是“X”字形。链表相交的物理意义其实是一个节点既被链表A的某个节点指向也被链表B的某个节点指向。这道题的暴力做法是遍历链表A的每个节点再遍历链表B看指针是否相同时间复杂度O(m*n)。面试官肯定不满意。高效做法有两种哈希表法和双指针对齐法。训练营主要推荐双指针。3.2 对齐末端法的工作原理双指针解法核心是既然从交点到最后是共用的那么两个链表不同的部分只可能在交点之前。如果把两个链表“末端对齐”——也就是让较长的链表先走差值步然后两个指针同步走第一个相遇的节点就是交点。用例子说明链表A长5个节点链表B长3个节点如果它们相交交点不可能在A的前3个节点之外和B的整个部分其实交点后的长度是相同的所以交点一定离两个链表末端有相同的距离。因此链表A比链表B多出的两个节点肯定在交点之前。让A的指针先走2步然后两个指针一步一步走当它们指向同一个节点时就是交点。如果走到末尾还没有相交返回null。这里需要注意链表相交是“指针相同”而非“值相同”。所以我写代码时判断条件一定用节点指针本身进行比较不要用val。3.3 实现代码与常见疑问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 (lenA lenB) { swap(lenA, lenB); swap(curA, curB); } int gap lenA - lenB; // 长链表先走gap步 while (gap--) { curA curA-next; } // 同步走 while (curA ! nullptr curB ! nullptr) { if (curA curB) return curA; curA curA-next; curB curB-next; } return nullptr; }这个代码如果两个链表长度不同通过swap让curA始终指向较长的链表。这是一种省事的写法但稍微有点绕。如果你不想用swap也可以写if分支。常见疑问一如果两个链表不相交会不会死循环不会因为同步走时它们最终都会到达null循环条件curA ! nullptr curB ! nullptr会终止最后返回null。常见疑问二为什么不能用“值相等”判断因为不同链表中值相同的节点可能很多而且题目要求是“同一个节点”也就是内存地址相同。只有指针比较才靠谱。常见疑问三能不能用哈希表能先把链表A的所有节点指针放入哈希表再遍历链表B第一个在哈希表中出现的节点就是交点。时间复杂度O(mn)空间复杂度O(m)。面试时可以提一下但双指针法空间O(1)更优。3.4 我踩过的坑第一次写这道题时我只计算了长度但没有处理“一个链表为空”的情况导致求gap时出现负数或未定义行为。后来加上长度判断和swap后就稳定了。另外测试时我喜欢自己构造两个相交链表结构上要注意两个链表必须共享后续节点所以不能简单地创建两个独立链表然后把它们的尾部改成相同值的节点而要让它们实际指向同一块内存。比如// 构造相交 ListNode* common new ListNode(8); common-next new ListNode(4); ListNode* headA new ListNode(1); headA-next new ListNode(3); headA-next-next common; ListNode* headB new ListNode(2); headB-next common;如果不注意这个很容易造出错误用例导致测试结果不准。4. 环形链表IILeetCode 1424.1 涉及的知识点和快慢指针思路这道题是链表题里综合难度较高的一题要解决两个问题第一判断链表是否有环第二如果有环找出环的入口节点。在力扣上这题的输入会比较特殊因为题目给了pos表示环入口位置但我们做题时使用的是传入的head不能直接知道入口必须通过快慢指针来推导。先解决第一问。常规做法是快慢指针慢指针每次走一步快指针每次走两步。如果链表无环快指针会先到达null如果有环快指针会进入环内一直绕圈最终会追上慢指针。这个判断方法很好理解就像两个人在操场上跑步一个快一个慢快的人迟早会套圈追上慢的人。但为什么快指针每次是“两步”而不是三步、四步其实三步也可以追上但两步是效率与判定的平衡。更关键的是两步的设定让后续推导环入口变得简单。如果一步快慢指针速度一样永不追上如果三步算法也正确但追击过程中可能“跳过”慢指针需要更仔细的边界处理而且从环入口推导的数学关系会变复杂。4.2 数学推导相遇点、头节点与入口的关系这是本题最核心的部分。假设从头节点到环入口的距离是x节点数环入口到快慢指针第一次相遇点的距离是y相遇点继续走到环入口的距离是z。那么环的周长是yz。慢指针走过的距离x y这里要说明一点慢指针进环后走的第一圈内一定被快指针追上不会走第二圈因为快指针相对慢指针每次多走一步绕环一圈就能追上。快指针走过的距离设入环前走了x入环后在环内走了若干圈设圈数为n从入口走了y到达相遇点所以快指针总距离是x n*(yz) y。由于快指针速度是慢指针的两倍相同时间内快指针距离是慢指针的两倍所以2*(x y) x n*(yz) y化简得到x y n*(yz)再变形x n*(yz) - y (n-1)*(yz) z当n1时x z。这意味着从头节点到环入口的距离等于从相遇点继续走到环入口的距离。这是一个非常重要的结论。即使n大于1公式中(n-1)*(yz)是环周长的整数倍说明从相遇点走z到达入口后再绕几圈也仍然在入口。所以结论依然成立如果一个指针从头节点出发另一个指针从相遇点出发每次都走一步它们必然会在环入口处相遇。因此整个算法的流程是快慢指针从头节点出发快指针每次两步慢指针每次一步。如果快指针遇到null说明无环返回null。第一次相遇时让一个指针从头节点重新出发另一个指针在原地两个指针每次都走一步。再次相遇的位置就是环入口。4.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) { // 有环找入口 ListNode* index1 head; ListNode* index2 fast; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; }这段代码在LeetCode上测试是没问题的。但我在本地测试时需要构造带环链表这里有个大坑如果用普通构造方式很容易构造出无效环导致程序死循环。比如ListNode* head new ListNode(3); ListNode* node2 new ListNode(2); ListNode* node0 new ListNode(0); ListNode* node4 new ListNode(-4); head-next node2; node2-next node0; node0-next node4; node4-next node2; // 环入口是node2注意node4-next指向node2而不是node2-next。如果指向node0那这三个节点会形成一个更小的环node2、node0、node4都不在环外入口就不一样了。另一个坑在第二段我的代码用ListNode* index1 head; ListNode* index2 fast;这里fast就是相遇点。很多同学写成index2 slow其实一样的因为相遇时slow和fast指向同一个节点。但要确保不是null。在while循环结束后index1和index2相等返回。4.4 为什么n1就够以及快指针的步长有些同学会问如果快指针在环内走了不止一圈公式里n1那x (n-1)*(yz)z怎么看其实代码不用区分n是多少。因为从相遇点出发走z步到入口若走(n-1)*(yz)z中间绕了n-1圈最后还是回到入口。所以双指针从头和相遇点同时走每次都一步它们会在入口相遇但要注意从头出发的指针走了x步到达入口从相遇点出发的指针走了z步也到达入口但由于yz0它们两个必须同时到达入口我们来验证从头指针到达入口时走了x步由公式x (n-1)*(yz)z也就是说从相遇点出发的指针需要走同样多的步数才能和从头指针相遇吗实际上代码中while循环直到两个指针相遇才停。从头出发的指针走x步到达入口时从相遇点出发的指针也走了x步由于xz整圈数所以它此时也在入口。因此它们会在入口相遇。如果环很大x很大它们也会继续走直到同时到达入口。这一步推导很关键我建议你动手画一个带环链表把x、y、z标出来再用一个短的环比如3个节点验证一下会特别清晰。快指针步长为什么不能是1因为快慢速度一样永远追不上。那步长3可不可以判断环没问题但找入口推导就会变成3*(xy)的等式同样能推出类似结论但可能涉及倍数变化需要快指针多绕圈。但两步是代码随想录和大多数面试标准直接记住两步就好。4.5 常见失败点和测试技巧这道题最常见的失败原因是忘记处理fast-next为空的情况。如果链表是线性无环fast会走到null如果只判断fast ! nullptr那么fast fast-next-next时如果fast-next本身就是null就会解引用空指针。所以循环条件必须是fast ! nullptr fast-next ! nullptr。还有一个好用的测试技巧当你想验证算法是否找到正确入口时可以让节点结构里加一个val标记打印节点的val。但不要只通过val来判断入口因为可能有重复值。5. 今天的题目总结与实用技巧5.1 四道题的核心共通点今天这四道题表面上是四道题实际上是两个核心技巧的反复应用。第一个技巧是虚拟头节点。在第24题和第19题里虚拟头节点让我们免去了对头节点特殊情况的讨论。删除头节点、交换前两个节点这些问题在有了dummyHead后都变得和其他节点一样。实际上凡是涉及“第一个节点可能被修改或删除”的链表题无脑加虚拟头节点几乎总是对的。第二个技巧是双指针。第19题用了快慢指针的差速第02.07题用了“先走差值”的双指针第142题用了快慢指针判环加相遇。双指针在链表里的三兄弟前后指针倒数第N个、并行指针相交、快慢差速指针环。把这三种理解透很多链表题都能迎刃而解。另外第24题的指针重连三步本质上也是对链表插入和删除操作的变形。我建议你在刷题时每一个操作都在草稿纸上画出指针变化画着画着就懂了。5.2 我个人的刷题节奏和debug经验今天这四道题我实际用时大概三个小时。前两题比较顺利第三题在构造测试用例上花了不少时间第四题在推导公式上卡了一会儿。如果你也卡住我建议你换一种方式不看题解自己先画图推导再对照代码。尤其是环形链表II如果你只是背代码过两天一定会忘。必须把x (n-1)*(yz)z这个式子亲手推导一遍。debug时链表题的输出结果可以用一个辅助函数打印链表void printList(ListNode* head, int count 20) { ListNode* cur head; while (cur ! nullptr count--) { cout cur-val - ; cur cur-next; } cout null endl; }注意对于有环链表这个打印函数会无限循环所以要加一个count限制。我在本地测试环形链表时就遇到过程序跑完不结束的情况后来加了count才发现环构造对了只是打印到环里出不来。这是正常的打印有环链表一定要限制次数。5.3 再分享一个用C写链表题的经验C写链表题最烦的就是内存管理。LeetCode上不需要释放内存但本地测试时如果不释放内存泄漏较多。养成好习惯的话每个new出来的节点都要对应delete。不过链表的delete要小心顺序先保存下一个节点再删除当前节点。尤其在做删除节点类题目时删除被删除节点后不要再去访问它的next。另外现代C可以多用智能指针但LeetCode默认是裸指针面试手撕也是裸指针所以训练还是以裸指针为主。如果你用Python刷题因为Python有自动垃圾回收不需要关心这些但也要知道指针的引用方式。最后想说的是链表题刷多了你会发现它们不仅仅是“数据结构题”更是在训练你一种思维在操作一个只有前驱和后续的世界里你怎么在只能向后走的约束下精确地找到目标位置。当你把今天这四道题吃透后面再遇到LRU缓存、合并K个链表等更复杂的题时你会感谢今天的积累。第四天还只是一个开始坚持住链表这座山翻过去后后面就是一马平川了。