四道链表题一个共同套路虚拟头节点与双指针思维先说说这四道题的共同点。为什么训练营要把它们安排在同一天因为它们本质上都在反复训练链表题的两个核心武器虚拟头节点dummy node和双指针。你把这套组合拳打熟练链表题基本就通了一半。适合谁看正在刷链表题但总觉得“代码能跑但思路不清晰”的同学或者面试前想快速梳理链表题型的人。我尽量把每道题的思考路径、易错点、边界情况都讲透你跟着走一遍比闷头刷十道题都强。1. 整体设计与思路拆解先建立链表题的操作系统1.1 虚拟头节点的本质统一边界操作链表题最烦的是什么不是逻辑难而是边界情况多。头节点被删了怎么办链表为空怎么办只有两个节点怎么办每次都要写if判断写多了就乱。虚拟头节点的出现就是为了解决这个问题。做法很简单在真正的头节点之前先挂一个dummy节点它的next指向真正的头节点。这样一来头节点变成了“普通节点”你对头节点的操作和其他节点完全一样不需要单独写特殊逻辑。这个思路跟操作系统里的“虚拟内存”有点像——用一个抽象层把复杂的物理细节统一掉上层只管用统一的接口操作。链表里的dummy节点就是这个抽象层让“删除头节点”和“删除中间节点”变成同一种操作。提示dummy节点不要命名为head否则代码读起来会混淆。习惯上叫dummyHead或dummy即可它本身的值val不重要永远不用。1.2 双指针链表题的半壁江山这一天四道题里有三道删除倒数第N个、链表相交、环形链表直接用了双指针剩下一道两两交换虽然名字不叫双指针但本质也是三个指针在配合操作。可见双指针在链表里的地位。双指针在链表里的应用主要分两种模型第一种快慢指针。一个走两步一个走一步利用速度差制造“里程差”用来找中点、判环、找倒数第N个节点。删除倒数第N个和环形链表都用的这个模型。第二种同速错位指针。两个指针速度一样但起点不一样制造“位置差”。链表相交是对齐两个链表长度后同时走本质就是消除起点差。环形链表找入环点时一个指针从头走一个从相遇点走也是同速起点差。在学习的时候把题目抽象成模型比单独背某道题的解法有用得多。因为面试官不会考原题但会考模型。1.3 画图大于看代码一个必须养成的习惯说个实在话链表题如果只盯着代码看永远学不明白。我见过太多同学刷链表题的方式是“看题 - 看答案 - 背代码”结果换一道就懵。链表这东西本质上是一堆节点在“串珠”你脑中必须有动态的画面感。我的习惯是拿到题目先在纸上画出链表的形态用一个方框代表节点用箭头代表next指针然后手动模拟几步操作再把指针移动的顺序写下来最后才写代码。这一步看着浪费时间实际是最省时间的。你手动模拟一遍走了几个分支边界情况在图纸上一目了然。后面每道题我都会先讲“图纸上的过程”再给代码就是为了帮你建立这种画面感。2. 两两交换链表中的节点指针顺序比你的记忆力更可靠2.1 题目拆解与易错点题目要求给定链表 1-2-3-4两两交换相邻节点变成 2-1-4-3。注意是交换节点本身不是交换节点的值。这俩的区别在于交换值不改结构实现简单但面试官通常不接受交换节点要重新接线考验对指针的理解。这道题的易错点有三个第一个交换之后前一个交换块和后一个交换块怎么接上很多人只盯着交换的那两个节点忘了前面还有一组结果链子在中间断开了。第二个循环条件怎么控制while循环的终止条件写错要么少处理一截要么访问空指针。这个必须结合链表长度的奇偶来讨论。第三个交换完成后cur指针该挪到哪如果挪错了下一轮交换的节点可能会被跳过一个。2.2 迭代实现与指针顺序详解先别急着看代码我们走一遍图纸。假设链表是 dummy - 1 - 2 - 3 - 4cur指向dummy。第一步我们要交换1和2。我们需要三个指针cur指向1的前驱、node1指向1、node2指向2。交换后链表应该变成 dummy - 2 - 1 - 3 - 4。关键操作顺序cur的next指向node22此时dummy连向2。node1的next指向node2的next3此时1连向3。node2的next指向node11此时2连向1。三步之后链表变成了 dummy - 2 - 1 - 3 - 4完美。然后cur怎么走注意下一轮要交换的是3和4而3的前驱是1所以cur应该移动到node1的位置也就是交换后处于第二位的那个节点。写成代码就是 cur cur-next-next因为在当前状态下cur-next是2cur-next-next是1。循环的终止条件是什么如果链表剩下至少两个节点才继续。具体来说就是 cur-next ! nullptr cur-next-next ! nullptr。前者对应链表长度为偶数时最后一组交换完cur移动到第二个节点位置此时cur-next可能为空后者对应链表长度为奇数时最后一组交换完后面只剩一个节点无法两两交换。完整代码ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; while (cur-next ! nullptr cur-next-next ! nullptr) { ListNode* node1 cur-next; ListNode* node2 cur-next-next; // 三步换向 cur-next node2; node1-next node2-next; node2-next node1; // cur前进到下一组的前驱位置 cur node1; } ListNode* result dummyHead-next; delete dummyHead; return result; }注意一定要先保存node1和node2的地址再开始改指向。因为当你执行cur-next node2之后原来的node1就“悬空”了——通过cur-next已经拿不到它了。写代码前把这一步想明白就不会出现“明明逻辑没错但链表断开”的情况。2.3 递归实现适合理解但别死磕这道题也可以递归。递归的逻辑很有意思先把前两个节点交换然后把后面的链表整体当作子问题处理。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; }这段代码很短每次递归处理一对节点返回处理后的新头节点。我个人的建议是递归解法看看就行面试时首选迭代。不是因为递归不好而是链表题在面试里往往要求你写清楚指针的移动过程迭代版更容易向面试官展示你的思路。如果你非要吃透递归记住一个规则递归函数返回的是“处理完这一对节点后这一段的头节点”。这样一层层往上整个链表就串起来了。3. 删除链表倒数第N个节点一次遍历的双指针解法3.1 从暴力到双指针的思路演变这道题的常规思路是先遍历一遍链表算出总长度L然后删除正数第L-N1个节点。这个思路没有任何问题面试时可以先提出来作为baseline但面试官紧接着会问“能不能只遍历一次”这就引出了双指针解法。想象有两个指针一个叫fast一个叫slow。fast先出发向前走n步。此时fast和slow之间相距n个节点。然后fast和slow每次都走一步保持这个距离。当fast走到链表末尾遇到nullptr时slow刚好在倒数第n1个节点也就是待删除节点的前驱位置。这跟生活中的排队思维很像两个人同时开始走一个人提前n步出发当前面的人到达终点时后面的人自然距离终点n步。你不用“数”总共有多少人只需要利用距离差。为了统一删除头节点的情况这里同样使用虚拟头节点。让slow从dummy出发当fast走到nullptr时slow指向的正好是待删除节点的前驱。3.2 代码实现与边界分析ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; // fast先走n步 while (n-- fast ! nullptr) { fast fast-next; } // 这里因为题目保证n有效所以不需要再判断fast是否为nullptr // 同步前进 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // 此时slow指向待删除节点的前驱 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; ListNode* result dummyHead-next; delete dummyHead; return result; }边界情况分析当n等于链表长度时fast会走到nullptr之后此时slow还在dummy位置slow-next就是原来的头节点删除后结果为空链表代码逻辑完全正确。当链表只有一个节点且n等于1时fast先走一步到nullptr同步循环不执行slow-next就是头节点直接删除结果为nullptr正确。我把这个解法吃过之后顺便说一下很多同学会踩的一个坑第二个while的终止条件是fast-next ! nullptr而不是fast ! nullptr。为什么要多绕一层因为当fast停在最后一个节点时slow恰好指向待删除节点的前驱。如果条件写成fast ! nullptrfast会多走一步变成nullptr而slow会走到待删除节点本身的位置那就很难删了——你找不到它的前驱了。这也是为什么链表删除题一定要记住单链表只有next指针你必须站在前驱的视角去删除。3.3 变体双指针模型的泛化其实这道题的双指针思想可以迁移到很多场景找链表中间节点快指针走两步慢指针走一步、判断链表是否有环快慢指针速度差、找两个链表的交点对齐长度后同步走。模型都是一样的无非是把“距离差”用不同的方式制造出来。我特别喜欢把它当作“双指针技术的三件套”来记制造距离差 - 保持距离差 - 利用距离差。删除倒数第N个是先生成距离差然后保持距离差走到底链表相交是先把长链表的指针多走几步消除距离差然后同步走。4. 链表相交两种方法一个核心4.1 题目本质这题不难但很多人想歪了题目给定两个链表需要找到它们相交的起始节点。很多同学第一反应是“比较节点的值”这是大坑。相交的定义是“两个链表在某个节点开始后面的节点完全共用”所以比较的应该是指针地址而不是值。两个不同位置的节点完全可以有相同的值但它们不算相交。题目要求的返回值是节点本身而且题目通常要求不能修改原链表。这里有个隐藏条件值得注意两个链表相交后因为单向链表只有一个next指针所以相交后的所有节点都是一样的。也就是说两个链表的结构是“Y”字形而不是“X”字形。理解这一点很重要它直接引出了下面两种解法。4.2 解法一先求长度再对齐末尾最直观的做法分别遍历两个链表求出各自的长度。然后让长链表的指针先走差值步让两个指针“站在同一起跑线”再同步向前走每走一步比较指针是否相等。第一个相等的节点就是交点如果走到nullptr都没有相等说明不相交。[\text{lengthA} - \text{lengthB} \quad (\text{假设A更长})]代码长这样ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA getLength(headA); int lenB getLength(headB); ListNode* pA headA; ListNode* pB headB; // 让pA指向更长的链表 if (lenA lenB) { swap(pA, pB); swap(lenA, lenB); } // 长链表先走差值步 int gap lenA - lenB; while (gap--) { pA pA-next; } // 同步走并比较 while (pA ! nullptr) { if (pA pB) return pA; pA pA-next; pB pB-next; } return nullptr; } int getLength(ListNode* head) { int len 0; while (head ! nullptr) { len; head head-next; } return len; }这个解法的核心思想是既然两个链表从交点开始就共享一条路径那么把两个指针挪到距离尾部相同的位置然后同步走它们一定会在交点相遇。如果快速判断两个链表的“后半段”是否重叠只需要看尾部节点是否相同。4.3 解法二双指针互相走完对方的链表优雅但需要理解这个解法我第一次看的时候觉得太巧妙了。两个指针pA和pB分别从headA和headB出发每次走一步。当pA走到末尾时让它跳到headB继续走当pB走到末尾时让它跳到headA继续走。这样两个指针都走了“链表A的长度 链表B的长度”这么多步会在交点相遇如果存在的话否则会同时走到nullptr。用公式解释一下假设链表A的长度为a链表B的长度为b它们的公共部分长度为c。那么pA走过的路径总长度是 a (b - c)先走完A再走B中不属于公共部分的部分pB走过的路径总长度是 b (a - c)。化简后发现两者相等都是 a b - c。所以它们最终会在交点的起始处相遇。代码非常简洁ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; // 不相交时返回nullptr因为两个指针同时到达尾部 }这段代码看起来有点“魔幻”但手动模拟几次就通了。我第一次用这段代码时犯了错——在pA为空时直接跳headB而不是先走完再跳导致死循环。正确的写法是每次只走一步走到nullptr时下一次循环才跳转。这串代码里 pA pA ? pA-next : headB 恰好实现了这个逻辑。两种解法选哪个我在训练营里看到很多同学推荐第二种因为它省去了先求长度的步骤。但我的建议是面试时先说第一种因为它更容易讲清楚面试官也更容易理解。说完之后可以补一句“如果要求代码更简洁还可以用互相交替走的方式”展示你对这个问题的深入理解。先把稳的答出来再把漂亮的亮出来这是面试的节奏。5. 环形链表II判断环与寻找入环点的完整推导5.1 题目含义与两问拆分这道题包含两个问题第一链表里有没有环第二如果有环环的入口在哪里很多同学在LeetCode上分别做过“环形链表”只判断有没有环和“环形链表II”找入口但第一次做这一版时没有把两个问题拆开思考导致过程混乱。判断有没有环用快慢指针即可快指针每次走两步慢指针每次走一步。如果链表无环快指针会先到达nullptr如果有环快指针会在环里不断打转最终和慢指针相遇。注意是“相遇”说明有环而不是“快指针超过慢指针”。为什么用两步而不是三步因为两步保证快慢指针的“相对速度”是1步慢指针不会跳过快指针速度差太大可能出现永不相遇的情况。找到相遇点之后第二个问题来袭怎么找环的入口看到这里你可以停下来想一下。如果只告诉你“快慢指针在环里的某点相遇了”你第一步会做什么很多方案是从相遇点出发继续走并计步绕环一圈就能得到环的长度k然后重新用两个指针一个从head出发一个从head前偏k步出发理论上也能找入口。但代码写起来略繁琐。实际上这道题有一个非常优雅的数学结论我第一次推完被震撼到了从相遇点到环入口的距离恰好等于从头节点到环入口的距离在不考虑环的长度的情况下。这直接导出一个简单解法把快指针或慢指针重新放到head两个指针都改成每次走一步继续走它们必定在环入口相遇。5.2 数学推导为什么两个同速指针必然在入环点相遇设链表头到环入口的节点数为a环入口到快慢指针第一次相遇点的节点数为b环的总长度为L从入口开始绕一圈回到入口的节点数。快指针速度是慢指针的两倍。当两指针第一次相遇时慢指针走了 (a b) 步快指针走了 (a b nL) 步其中 (n) 是快指针在环里多绕的圈数至少为1。因为快指针的速度是慢指针的两倍所以 [ 2(a b) a b nL ] [ a b nL ] [ a nL - b ]看右边这个式子(nL) 是环长度的倍数减去 (b) 之后剩下的步数正好是从相遇点继续走到环入口的“剩余步数”因为相遇点到入口的距离就是 (L-b) 加上若干圈。如果 (n1)(a L-b)如果 (n\geq 1)同样成立因为绕了n圈最终都要回到入口。所以结论非常干净从头节点走到入环点的步数等于从相遇点继续走到入环点的步数可能多绕了几圈但关键结论不变。于是只要把慢指针放回head两个指针都每次走一步它们一定会同时在入环点相遇。这个结论第一次看可能有点绕但你可以用纸笔画一个小环手动模拟一下比如链表头到入口有3个节点环长4个节点。让快慢指针走一遍找到相遇点再放回头节点走一遍你不仅会发现它们确实在入口相遇还会彻底明白刚才的推导。画图永远是最好的老师。5.3 完整代码实现ListNode* detectCycle(ListNode* head) { ListNode* fast head; ListNode* slow head; // 第一步判断是否有环找到相遇点 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; // 慢指针走一步 fast fast-next-next; // 快指针走两步 if (slow fast) { // 有环且相遇 break; } } // 如果没有环fast走到nullptr if (fast nullptr || fast-next nullptr) { return nullptr; } // 第二步两个指针重新从头和相遇点出发同速前进 ListNode* p1 head; ListNode* p2 slow; // 即相遇点 while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; }这段代码有几点需要强调第一while循环的条件是fast ! nullptr fast-next ! nullptr。因为快指针走两步如果它在某个节点之后没有下一个节点了说明链表没有环。这个条件也天然处理了空链表和单节点链表的情况。第二跳出循环后判断fast nullptr || fast-next nullptr。这是因为刚才的while有两种出口一是遇到环内相遇break出来二是快指针触底循环条件不满足正常退出。后者说明没有环返回nullptr即可。第三p1和p2相遇时就是环的入口节点。这一步的数学依据就是上面的推导写代码的时候心里要有底不能“感觉应该是这样”就算完。如果面试时想用更稳妥的“哈希集合”解法也可以遍历每个节点用哈希集合记录地址如果遇到已经在集合里的节点那它就是环的入口。这个解法思路简单空间复杂度O(n)。面试时如果先问“能不能用额外空间”说明对方期待的是双指针的O(1)解法如果能接受额外空间哈希法是最好讲的备选。6. 常见问题与排查技巧实录6.1 高频报错与排查速查表我把训练营里这几天常见的问题和解决办法整理成了表格对照自查即可现象原因排查方法运行超时死循环循环条件写错如 while(fast ! slow) 但没有考虑无环情况检查 fast 或 slow 是否可能在环内追不上或者循环退出条件缺失空指针异常访问了 cur-next-next但 cur-next 已经是 null在每次访问前判断 cur-next 是否为空特别是链表中部操作两两交换后链表断开交换节点的最后一步没有把 node2 连接到 node1或者忘记把 node1 连到 node2-next在纸上画图模拟三步操作按顺序写代码删除倒数第N个时删错节点快指针先走的步数不对或者第二个循环的终止条件有误记住快指针先走 n 步然后while (fast-next ! nullptr)slow 指向的是前驱环形链表找入口时死循环没有先判断是否有环就进入找入口的循环先确认 fast 是否在 null 处退出再进入第二阶段链表相交比较了值而非地址用pA-val pB-val判断相交相交判断应该用pA pB6.2 边界测试清单每次交代码前检查一遍链表题能不能过边界情况占了八成功劳。每道题写完代码我都会用下面这份清单自测一遍空链表head nullptr只有一个节点只有两个节点删除倒数第1个节点即尾节点删除倒数第n个节点其中n等于链表长度即头节点链表长度恰好为偶数、奇数各测一遍相交的两个链表长度相等 / 不相等环形链表入口恰好是头节点环形链表入口在链表尾部入口的next指向头即首尾相连的环比如两两交换用空链表跑一遍看会不会崩用奇数长度链表跑一遍看最后一个孤节点会不会被错误处理。删除倒数第N个删头节点时务必验证删除后的链表是否完整。链表相交两条链表的长度差恰好是0、1、大于1分别测试。环形链表入口是头节点这种情况最容易漏。6.3 训练营打卡的独家小技巧分享几个我在训练营里学到的实用技巧。第一个写链表代码前先在代码注释里写下指针移动的顺序。比如两两交换我总在代码最上面写上// cur - node1 - node2 - nextNode // 交换后cur - node2 - node1 - nextNode写注释的过程就是帮你想清楚的过程。等你把注释写清楚了代码往往只需要几分钟。第二个遇到“删除节点”的题一定要站在“前驱节点”的视角去想。单链表只能通过next指针访问下一个节点所以删除谁就得拿到谁的前驱。虚拟头节点的作用就是让头节点也有前驱。第三个在LeetCode或本地上跑调试时自己写一个打印链表的函数。每次操作完打印一遍链表用肉眼看看节点连接有没有断。这个习惯陪我解决了好多棘手的bug比盯着代码看半小时效率高得多。第四个遇到数学推导比如环形链表不要害怕。先用具体数字比如a3, b2代入演算一遍你会发现公式只是把具体规律抽象化了。推导通了这个解法一辈子忘不掉。到这一步回头再看这四道题你可能会发现两两交换练的是“指针重新穿线”删除倒数第N个练的是“双指针制造距离差”链表相交练的是“对齐起点”环形链表练的是“快慢指针和数学规律的结合”。每一道刷完都要问自己这道题的核心模型是什么哪里最容易出错下次遇到类似题我能一眼识别吗我在实际做这四道题时花了比预期长得多的时间尤其是环形链表的数学推导第一遍没推明白后来画了整整三页纸才算彻底通透。但从那以后链表题的指针移动我再也没有犯过“写一步漏一步”的毛病。做题的意义不在于“AC那一刻的爽感”而在于AC之前那段痛苦的思考——那才是真正长本事的地方。如果你今天也卡在链表题上不要急。先放下代码拿出草稿纸把链表的形状画出来把指针的移动画出来把边界情况画出来。画完你会发现自己离答案已经不远了。这四道题刷完链表题的大门基本算是正式推开了后面无论是反转链表、合并链表还是各种链表变体你都会觉得“这题我见过”。