链表双指针与虚拟头节点：四道经典题一次说透

我在代码随想录训练营刷到第4天这一天是妥妥的链表专题四道题分别是LeetCode 24两两交换链表元素、19删除链表的倒数第N个节点、160相交链表、142环形链表II。说实话链表题单独看每一道都觉得这不就是改改指针吗但真正上手你会发现要么访问空指针要么出现环导致死循环要么把自己绕晕。这四道题里24和19考的是对节点指针的精确定位160和142则把双指针玩出了花。如果你觉得这几道题已经刷过很多次但还是会忘那这篇总结值得看完我会把每道题的思路推导和踩坑过程全部写出来。1. 这四道题为什么值得放在同一天刷1.1 一天四道链表题核心其实是一个前驱思维链表题的坑大家都清楚顺序表你拿到下标就能干活链表不行任何增删操作都绕不开一个前置条件——先定位到目标节点的前驱节点。删除一个节点你改的是前一个节点的next交换两个节点你改的是上一组节点带过来的next找相交点、找环入口本质上也是寻找某个特殊位置的前后关系。四道题如果你一个个孤立着刷很快就忘如果带着找前驱这个视角去刷等于一天之内把链表最核心的几种操作全过了一遍。举个例子19题删除倒数第N个节点大多数人第一反应是走L-N步就能到目标节点但真到删除的时候才发现你要拿到的是目标节点的前驱否则改不了指针。24题看似是交换两个节点但整个操作结束时真正要更新的是上一组节点最后的那个尾巴。160和142更隐蔽它们表面上是找点本质上是让两个指针在特定条件下达成交汇。可以说这四道题练的其实是同一套底层思维。1.2 四道题的技术点横向对比题目核心考点能带走的技术点24 两两交换链表元素虚拟头节点 四指针接力变换头节点可能变动的场景统一用虚拟头节点兜底19 删除链表倒数第N个节点双指针先走N步一次遍历拿到倒数第N个节点的前驱160 相交链表两条链互补路程的相遇总路径相同交点自然出现142 环形链表II快慢指针 数学等量代换fast走两步时相遇点与入口存在固定距离关系从难度梯度上看这四道题也有讲究。24题解决的是单链表内部的指针重新组合19题解决的是单链表上未知长度的定位问题160题把视角拉升到两条链之间的长度差消除142题则是带环链表上的追及运动。按这个顺序刷相当于从怎么改指针练到怎么用双指针建模。2. 24题两两交换链表元素虚拟头节点拿下指针变换2.1 这道题到底在考什么题目看起来人畜无害1-2-3-4输出2-1-4-3奇数个节点时最后一个不交换。难点在于题目要求的是真正改变节点的连接关系而不是交换value。有些人图省事直接swap两个节点的val不是说不行但刷题和面试里通常不建议这样——节点里往往绑定着额外信息而且题目训练的就是指针操作。你要是上来就交换val等于白练了。我第一次自己写的时候以为把逻辑理成1指向32指向1但2怎么放在开头就完事了。结果一写就碰到问题当你把节点1的next改成3之后节点2在哪早就丢了。这就是为什么很多老手强调链表的指针变换一定要先记住所有会断掉连接的节点。这道题看似简单实际是训练这个习惯最好的题目之一。2.2 画图拆解指针变换的四个步骤用一个虚拟头节点dummyHead指向head然后让cur指针从dummyHead出发每次处理两个节点。用文字描述这个过程记下当前要交换的两个节点。first等于cur-nextsecond等于cur-next-next。先把cur-next指向second这一步让上一组节点和新一组第二个节点接上。再让first-next指向second-next把本组第一个节点接到下一组节点的头上。最后让second-next指向first完成本组两个节点的交换。四个步骤做完cur再移动到first。这里的first经过交换之后已经成为这一组节点里的第二个节点正好也是下一组节点的前驱。循环条件非常关键cur-next不为空且cur-next-next不为空翻译成人话就是后面至少还剩两个节点才值得交换。为什么必须用虚拟头节点因为头节点本身也会作为first参与交换没有dummyHead的话第一步cur-nextsecond根本找不到cur的上一级。用了dummyHead所有节点都统一成有前驱的节点代码不用为头节点单开分支。2.3 代码实现与边界条件验证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* first cur-next; ListNode* second cur-next-next; cur-next second; first-next second-next; second-next first; cur first; } ListNode* result dummyHead-next; delete dummyHead; return result; } };边界情况可以这样验证空链表dummyHead-next是nullptr循环条件不成立返回nullptr。单个节点cur-next-next是nullptr循环不执行返回原head。两个节点交换一次cur走到first原节点1此时cur-next是原来1的next也就是nullptr循环退出。三个节点交换第一组之后cur-next指向节点3但cur-next-next是nullptr循环退出节点3保持不动。结果2-1-3正确。这里要特别警惕一个新手做法交换完之后把cur写成cur-next-next。第一次交换没问题第二次交换就漏节点了。因为交换完之后本组第二个节点已经不是第二节点而是first所以必须直接等于first。2.4 递归解法和迭代的取舍递归的写法非常短class Solution { public: ListNode* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* next head-next; head-next swapPairs(next-next); next-next head; return next; } };理解递归解法的关键是swapPairs(next-next)返回的是后面所有节点两两交换后的新头节点。head-next先接到这个返回值再把next-next指向head链表就顺时针接上了。这写法很优雅但面试时我仍然建议优先写迭代。原因有两点递归在链表很长时有栈溢出风险另一方面迭代有利于把指针关系一步一步讲清楚面试官更容易看出你没有背答案。3. 19题删除链表的倒数第N个节点双指针先走N步的来历3.1 两次遍历容易一次遍历的原理是什么先数一遍链表长度L再走L-N步删节点这是两次遍历肯定能写出来。但LeetCode 19题的进阶要求是one pass。很多人觉得不可能不知道链表总长度怎么知道第L-N1个节点在哪双指针给出的方案是长度补偿fast先走N步此时它距末尾还剩L-N步。fast和slow同时以相同速度前进当fast走到末尾时它一共又走了L-N步。而slow从虚拟头节点出发也同步走了L-N步于是正好停在目标节点的前驱位置。这个剩下的路程就是补偿的关键。我第一次推导的时候是用一个更直白的视角倒数第N个节点从后往前数它的前驱距离末尾正好是N步。所以谁先走N步谁就先到达从后往前数N步的位置另一个slow要做的就是把这段路程完整复刻一遍。双指针之间始终保持N步的相对距离这个距离就是倒数N的核心。3.2 多走一步的细节与代码逐句解析代码是这样写的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; } while (fast-next ! nullptr) { fast fast-next; slow slow-next; } ListNode* delNode slow-next; slow-next delNode-next; delete delNode; ListNode* result dummyHead-next; delete dummyHead; return result; } };注意第一个while结束之后fast已经走了N步此时fast与dummyHead之间距离是N个节点。第二个while为什么用fast-next ! nullptr而不是fast ! nullptr因为我们要让slow停在待删节点的前驱。如果第二个循环走到fast成为nullptr才停slow会直接指到待删节点本身反而没法删。用fast-next判空相当于fast停在最后一个真实节点上slow恰好往前一位落点就是待删节点的前驱。这一点也是很多人的迷思到底先走N步还是N1步我推荐这种写法它天然处理了N等于链表长度的情况不需要额外讨论。3.3 三个必测边界用例链表只有1个节点N1fast先走1步到达head第二个循环fast-next为nullptr不执行。slow停在dummyHeaddelNode正好是head删除后返回nullptr。链表有5个节点N5fast先走5步到达第5个节点fast-next为nullptr第二个循环同样不执行。slow停在dummyHead删除的是head节点。这正说明为什么虚拟头节点在这里是必须的——不使用dummyHead删除头节点就得单独写if。链表有5个节点N2fast先走2步到第2个节点直到fast走到第5个节点时slow从dummyHead走到第3个节点。第3个节点的next是第4个节点也就是倒数第2个节点删除它剩下1-2-3-5正确。这道题你还可以换一种思路验证fast和slow之间始终隔着N个节点当fast停在末端时slow离末端也是N个节点。这本质上和倒数第N个是同一个几何关系。4. 160题相交链表让两个指针跑出相同的里程4.1 暴力法和哈希表的天然缺陷最直白的做法遍历A链每个节点都去B链走一遍时间是O(m*n)基本会被LeetCode判超时。再进一步把A链所有节点地址放入哈希集合遍历B链时逐个查时间O(mn)空间O(mn)这能过但不符合进阶要求的空间O(1)。为什么这题要卡空间因为相交链表的场景非常常见——比如两个服务共用同一批数据节点你想在O(1)额外空间内找到它们的公共起点。哈希表做法只能说是一个过渡方案考察的意义不大。4.2 双指针互访为什么总路程相同就能相遇经典解法是让两个指针pA和pB分别从headA、headB出发。pA走完A链后切到headB继续走pB走完B链后切到headA继续走。当它们相遇时就是第一个公共节点。推导的核心是总路程相同。设A链独有部分长度为aB链独有部分长度为b公共部分长度为c。pA到达交点前走的路程是acbpB到达交点前走的路程是bca。两者完全相等而两个指针速度相同所以必然同时踩到交点。打个比方两个人从两条不同的小路出发速度一样。如果两条路最后汇成一条大路而一个人先走小路A再走小路B另一个人先走小路B再走小路A两人走的总距离相同自然在大路的同一处碰面。需要注意的是不相交的情况。此时c等于0pA走完ab后变成nullptrpB走完ba后也变成nullptr两个指针都为空循环退出返回nullptr。这个行为是自动的不需要额外判断。4.3 代码上的两个易错点class Solution { public: 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; } };第一个易错点是循环条件。while(pA ! pB)天然把两个指针都变成nullptr作为退出条件此时pA和pB都等于nullptr返回pA就是nullptr。如果你把循环条件写成while(pA-next ! nullptr)就会丢失处理不相交情况的能力。第二个易错点是切换时机。必须在pA为空时才切到headB不能提前切。提前切会导致两个指针的相对位置错乱追不上交点。有些写法是pA-next为空就切这样更危险因为A链最后一个节点会被跳过相交点如果恰好在这个节点上就漏掉了。这道题还有另一种标准做法先分别求出A、B长度让长链的指针先走长度差再同步走。这个方法的推导更直观适合在面试中先用它讲思路再给互访版本代码。两种都要会。5. 142题环形链表II从相遇到入口的数学推导5.1 快慢指针怎么判断有环判断链表有没有环是141题的事方法大家都会fast每次走两步slow每次走一步。如果没环fast会先碰到nullptr如果有环fast和slow一定在环内某个点相遇。原因在于进入环之后fast相对slow每轮追近一步fast走2步、slow走1步每轮差距缩小1步环的周长有限快指针迟早追上慢指针。这道题直接写就行但要注意while循环里必须判断fast ! nullptr fast-next ! nullptr。如果fast-next已经是nullptr再访问fast-next-next就崩了。链表只有一个节点或者普通无环链表的场景这个判断就把它兜住了。5.2 几个变量和等式的完整推导142题真正的难点是找入口。先说结论fast和slow第一次相遇后让一个指针从head重新出发另一个指针留在相遇点两个指针都一次走一步再次相遇的位置就是环入口。这个结论很多人背下来了但不明白为什么。我用一套变量把它推清楚设链表起点到环入口的距离为a环入口顺着链表方向到第一次相遇点的距离为b从相遇点继续前进回到环入口的距离为c。环的周长就是bc。slow从起点到相遇点一共走了ab步。fast从起点到相遇点一定比slow多走了几圈假设多走了k圈那么fast走的路程是abk(bc)。由于fast速度是slow的两倍时间相同路程也是两倍所以2(ab) abk(bc)移项化简得到ab k(bc)再继续变形a k(bc) - b (k-1)(bc) c这个式子的含义是从链表起点出发走a步到达入口等于从相遇点出发走c步到达入口然后再绕环若干圈。所以当head处的指针走a步到入口时相遇点处的指针绕了c步加若干整圈也恰好到达入口。两者就在入口处相遇。5.3 代码实现与无环情况的容错class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast head; ListNode* slow head; while (fast ! nullptr fast-next ! nullptr) { fast fast-next-next; slow slow-next; if (fast slow) { fast head; while (fast ! slow) { fast fast-next; slow slow-next; } return slow; } } return nullptr; } };这段代码容易出错的点有三个。第一个是相遇后fasthead这个操作。很多人会写成fast head-next那就和数学推导对不上了。第二步必须是从起点出发的指针和从相遇点出发的指针同时一步一步走。第二个是二次相遇的位置不是原来的相遇点。我第一次理解的时候绕了很久两个指针一个从head走一个从相遇点走都走一步那不是很快就会重新在原来的相遇点碰上吗其实不会。因为相遇点到头需要走过c步才到入口而head到入口需要a步两者路程相等所以它们在入口就碰上了根本不会回到第一次相遇点。第三个是只有一个节点且成环的情况。比如head-next指向head自己slow第一次移动后到headfast移动后也回到head两者相等。然后fastheadwhile立刻满足fastslow返回head正确。6. 四道题刷完我把链表双指针的套路梳了一遍6.1 找到前驱是链表操作的总钥匙四道题做完如果你问我最大的收获是什么我会说是前驱思维。链表里几乎所有操作最后都归结为一个问题怎么拿到你真正要操作那个节点的前驱。操作真正要拿到的节点删除倒数第N个节点倒数第N个节点的前驱两两交换上一组交换后的尾节点也就是cur相交链表两个指针第一次踩到的同一个节点环形入口快慢指针相遇后由头节点指针和相遇点指针共同追到的入口你把四道题套进这张表会发现很多解法不是背出来的而是被前驱需求倒逼出来的。比如19题没有虚拟头节点删除头节点时就没有前驱所以要造一个24题不搞虚拟头节点头节点作为first时就没人帮它连接前驱。这个思维比记住某个题的具体步骤重要得多。6.2 三种双指针形态的适用场景这四道题里的双指针可以分成三类双指针形态代表题目核心逻辑同速双指针其中一个先走N步19题用先走补偿未知的链表长度同速双指针互换起始链表160题让总行走路程相等不同速双指针142题用速度差制造追及相遇掌握了这三种形态很多链表题可以照猫画虎。比如LeetCode 876找链表中点就是快指针走两步、慢指针走一步fast到末尾时slow刚好在中点再比如LeetCode 143重排链表第一步也是用快慢指针找到中点再把后半段反转后交错合并。可以说三种形态就是链表双指针题的骨架。6.3 关于这一天的刷题顺序与扩展练习我个人的建议是打乱题号按虚拟头节点 - 双指针 - 数学推导的顺序来刷。先做24和19把前驱和虚拟头节点的感觉建立起来再做160体会双指针如何通过路程互补解决问题最后做142因为它的推导最抽象放最后不容易劝退自己。辅助练习可以安排141环形链表是142的前置先做141热身后做142876链表中点、206反转链表、234回文链表、143重排链表都是同一套工具链。题目不难但每一道都值得在纸上画一遍指针变换画完再写代码比直接看题解效率高很多。我这一年刷链表题最大的体会是链表题不怕慢就怕绕。慢一点把指针变化画清楚一次AC图省事直接改指针往往要在debug里浪费更多时间。四道题互相之间有很强的递进关系刷完再回头看你会发现第4天这个量级其实刚好——不多不少把链表最重要的几种考察方式全部覆盖了一遍。