如果你正在跟着代码随想录算法训练营打卡大概率会在第四天撞上这组题目LeetCode 24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。刷之前我觉得链表题无非就是把指针掰来掰去刷完之后我才意识到这四道题根本就是同一个主题的四个侧面——虚拟头节点怎么用、双指针怎么给链表定位、长度差怎么消除、追及问题怎么转化成数学公式。这篇文章我不打算把官方题解复述一遍而是从训练营学员最容易卡壳的地方切入把这四道题的设计意图和证明过程说清楚顺便整理一份可以直接复用的链表操作检查清单。非常适合正在跟着训练营打卡但被指针绕晕的学员也适合已经刷完一遍、想回头把链表底层套路系统整理一遍的朋友。1. 两两交换链表中的节点虚拟头节点才是整道题的灵魂1.1 为什么一上来就要造一个虚拟头节点先读题。给定 1 - 2 - 3 - 4要求返回 2 - 1 - 4 - 3。注意题目的限制条件不能只是单纯的改变节点内部的值也就是说必须真的去调整节点之间的 next 指向。我第一次写这道题时第一反应是直接从头节点开始交换。但很快发现一个尴尬的问题倒数第二个节点变成了新的头节点原来的 head 变量失效了后面所有逻辑都要针对头节点是否变化做特判。代码会写得又臭又长还容易漏。解决办法就是引入一个虚拟头节点 dummyHead让 dummyHead-next 永远指向真正的头节点。无论后面的节点怎么交换dummyHead 本身不发生移动最后直接返回 dummyHead-next 就是新链表。ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; // 后面逻辑 return dummyHead-next; }这里有一个很容易被忽略的好处dummyHead 让 cur 指针在遍历时始终指向一对待交换节点的前一个节点这样就不用区分当前操作的是不是头节点统一走同一套逻辑。这个思想在 19 题里还会再次出现。1.2 交换三连保存、重连、进位看图理解一下交换过程。假设当前状态是 dummyHead - node1 - node2 - nextPaircur 指向 dummyHead。我们要把 node1 和 node2 交换变成 dummyHead - node2 - node1 - nextPair然后 cur 前进到 node1继续处理下一对节点。我习惯用一个交换三连口诀先保存后继再改两条 next最后移动 cur。ListNode* tmp cur-next-next-next; // 保存 node2 之后的链表入口 cur-next cur-next-next; // 第 1 步指向 node2 cur-next-next tmp ? 原来的 node1 的位置 : nullptr; // 这一步需要先存 node1这里要特别小心上面这段代码是错的。因为在执行第 1 步之后原来的 node1 就被覆盖掉了必须提前保存。正确的写法是ListNode* tmp1 cur-next; // 保存 node1 ListNode* tmp2 cur-next-next-next; // 保存 node2 的下一个节点 cur-next cur-next-next; // cur 指向 node2 cur-next-next tmp1; // node2 指向 node1 tmp1-next tmp2; // node1 指向原来的后继 cur tmp1; // cur 移动tmp1 就是下一对节点的前驱这几行代码建议动手画图去理解而不是死背。我第一次没画图直接把 cur-next-next 改成了 node1结果后面半条链表直接丢了。链表题最大的特点就是这样只要有一条 next 指针没有正确接回去整条链就会断在某个地方。用生活化的例子来说这就好比排队的两个人要换位置。你先把排三以后的同学叫到一边站着tmp2然后让排二站到最前面排一站到排二后面最后把排三以后的同学重新拉回来接到队尾。只要有一环没接住队伍就散了。1.3 循环条件与奇数节点处理循环条件应该是 cur-next ! NULL cur-next-next ! NULL意思是当前待交换的一对节点必须都存在。如果链表节点数是奇数最后一个节点没有配对节点保持原样即可。很多新手会写成 while (cur-next ! NULL) 或者 while (cur ! NULL)这两种写法都会出问题。前者在只剩一个节点时cur-next-next 解引用空指针后者则会让 cur 直接走到链表末尾交换逻辑无法执行。建议用这几组测试用例自测空链表 []、单节点 [1]、双节点 [1,2]、三节点 [1,2,3]、四节点 [1,2,3,4]。尤其是奇数和偶数长度的链表都能跑通才说明循环边界没有问题。这道题的时间复杂度是 O(n)空间复杂度是 O(1)只使用了常数个临时指针变量。在训练营里这道题的通过率其实不算低但很多人是背下来的隔一天再写就卡住了。真正要掌握的是保存后继、重新接线、移动游标这个三件套。2. 删除链表的倒数第N个节点双指针的距离差才是关键2.1 先想清楚要删除的到底是哪个节点题目要求删除倒数第 N 个节点比如链表 1 - 2 - 3 - 4 - 5n 2删掉的是值为 4 的节点返回 1 - 2 - 3 - 5。最朴素的想法是两次遍历第一次算出链表的长度 len第二次走到第 len - n 个节点也就是待删除节点的前一个节点然后执行删除操作。这种方法当然能过但题目下面有一行进阶要求尝试使用一趟扫描实现。很多同学卡住是因为没有意识到一个关键点删除一个节点真正需要操作的是它的前驱节点。所以删除倒数第 N 个节点本质上等价于找到倒数第 N 1 个节点。只要能一次遍历定位到倒数第 N 1 个节点删除操作就顺理成章了。2.2 快慢指针怎么走距离差这里就是双指针登场的时候了。想象一个场景跑步比赛快的人先出了起跑线慢的人还在原地。如果快的人先跑出 N 1 步之后两个人以完全相同的速度前进那么当快的人到达终点时慢的人距离终点正好还有 N 1 步。放在链表场景里终点是 NULL慢的人刚好停在倒数第 N 1 个节点上。实现上通常会配合虚拟头节点。fast 和 slow 都从 dummyHead 出发fast 先走 n 步然后两个指针同步移动直到 fast-next NULL。此时 slow 正好指向倒数第 N 1 个节点。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; while (n-- fast ! NULL) { fast fast-next; } while (fast-next ! NULL) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; }注意这里 fast 只先走了 n 步而不是 n 1 步。原因是循环条件是 fast-next ! NULL它等价于让 fast 走到最后一个有效节点时停止。此时 slow 正好在待删节点的前驱位置。如果你让 fast 先走 n 1 步那循环条件就得改成 fast ! NULL两者的本质是一样的不要记混。我见过不少同学在这里纠结为什么不是 fast 先走 n 步、然后 fast 和 slow 一起走、fast 为 NULL 时 slow 正好是倒数第 N 个节点这样确实定位到了目标节点本身但单链表无法直接删除当前节点除非再多维护一个前驱指针复杂度反而更高了。2.3 虚拟头节点的作用在这里更明显如果没有 dummyHead删除头节点 return head-next 需要单独处理。加入 dummyHead 之后fast 和 slow 都从 dummyHead 出发哪怕要删除的就是原链表的头节点slow 依然能指向它的前驱dummyHead不需要任何特判。这道题还有一个延伸考点如果不用双指针能不能用递归或栈实现可以。递归回溯的时候计数或者把节点全部压入栈弹出第 N 个删除都能做。但栈会引入 O(n) 的额外空间双指针是面试官最想听到的解法。边界测试建议覆盖单节点链表 n1、链表长度等于 n删头节点、链表长度为 n1删末尾节点、n 大于链表长度题目通常保证 n 有效但要心里有数。我在训练营里看到很多同学写这道题时一上来就求长度看到题目的进阶提示又不敢用双指针。其实双指针的本质就是把这个长度差提前算好利用两个指针之间的相对距离来确定位置。一旦理解了它是怎么消除第二次遍历的19 题基本不会忘。3. 链表相交长度差就是破局点3.1 相交的不是节点值是节点本身面试题 02.07 的表述很有意思给你两个单链表的头节点 headA 和 headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null。题目很阴险的一个细节是示例里的链表值是 4、1、8、4、5 和 5、0、1、8、4、5其中都出现了值为 1 和值为 8 的节点。很多人第一次做这道题会把节点值相等当成节点相交然后发现怎么都跑不对。链表相交的本质是指针地址相同。两个节点指向内存里的同一个对象它们的 val 当然相同但 val 相同不代表它们是同一个节点。举个例子链表达成 A 是 [1,9,1,2,4]B 是 [3,2,4]第一个共同的节点是值为 2 的那个节点而不是值为 1 的节点因为 A 里的 1 和 B 里的 1 不是同一个节点。想明白这一点后这道题的一切解法都建立在两个指针指向同一个地址这个判断上。3.2 解法一先把长的链表走掉差值再同步比较假设两条链表相交那么从交点开始它们后面部分的长度是完全相同的。所以如果在交点之前两条链表的长度不同只需要让较长的那条链表先走几个节点把长度差补平然后两条链表的指针保持同步前进第一个相同地址的节点就是交点。第一步求两条链表的长度第二步让长的先走 gap 步第三步同步遍历。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* curA headA; ListNode* curB headB; int lenA 0, lenB 0; while (curA ! NULL) { lenA; curA curA-next; } while (curB ! NULL) { lenB; curB curB-next; } curA headA; curB headB; if (lenB lenA) { swap(lenA, lenB); swap(curA, curB); } int gap lenA - lenB; while (gap--) { curA curA-next; } while (curA ! NULL curB ! NULL) { if (curA curB) return curA; curA curA-next; curB curB-next; } return NULL; }交换变量那一步是为了保证 curA 永远指向较长链表的头节点这样后面只需要一个 gap 变量就能统一处理不用写两套逻辑。这个习惯在写代码时可以经常用能省掉不少分支判断。3.3 解法二走完自己的路再去走别人的路第二种解法不需要求长度代码也短得多ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA NULL ? headB : pA-next; pB pB NULL ? headA : pB-next; } return pA; }核心思路是把 pA 想象成在走链表达成 链表 B这条路径pB 想象成在走链表 B 链表 A这条路径。两条路径的总长度完全相等如果两条链表相交pA 和 pB 必然在交点相遇如果不想交它们最终会同时走到 NULL退出循环并返回 NULL。为什么一定会在交点相遇设链表达成独立部分的长度为 a链表 B 独立部分的长度为 b公共部分的长度为 c。pA 走到交点需要经过 a c再走到链表 B 的末尾需要经过 bpB 走到交点需要经过 b c再走到链表达成的末尾需要经过 a。两者走的总距离都是 a b c所以在走过自己那条链表、再走对方独立部分时必然在同一个位置碰到。很多同学一开始不理解这个解法会觉得 pA 和 pB 怎么可能在不同长度链表上走到同一个节点。其实这就是把两条链表尾部对齐之后在起点处比较的一个变形。当 pA 走完链表达成就接着走链表 B 的头部相当于人为地把两条链表拼接成了 AB 和 BA它们共享同一个尾部交点之后的部分所以最后一段路是同步的。面试时如果让我推荐我会先说长度差对齐的解法因为它更好解释再补充一遍拼接解法展示自己知道更简洁的版本。两道题的代码都不长但要能画出两种思路的推导过程才算真正掌握。4. 环形链表II快慢指针以及那个绕不开的数学推导4.1 先判断有没有环快指针一次跳两步142 题是四道题里推导最重的一道也是训练营里讨论度最高的题之一。题目要求判断链表是否有环如果有返回环的入口节点。判断有没有环最经典的做法是快慢指针slow 每次走一步fast 每次走两步。如果链表里有环fast 迟早会在环里追上 slow因为它们进入环之后一个快一个慢运行轨迹是闭合的。这里经常有人问为什么快指针要一次走两步不能走三步吗理论上快指针一次走三步也可能追上但可能不够可靠因为当 slow 和 fast 都在环内运动时如果步长是 3存在一种情况是 fast 一次性跨过 slow导致它们永远错开。步长 2 时每经历一个时间单位fast 相对 slow 接近一步由于环是有限的闭环一定能追上。实现时要注意一个细节fast 每次跳两步前必须确认 fast ! NULL 且 fast-next ! NULL否则会空指针异常。这也是 while 循环条件的来源。ListNode* detectCycle(ListNode* head) { ListNode* fast head; ListNode* slow head; while (fast ! NULL fast-next ! NULL) { 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 NULL; }4.2 找入口的数学推导从相遇点出发再走一段就能到入口假设链表头到环入口的距离为 a环入口到快慢指针第一次相遇点的距离为 b相遇点继续沿着环走回环入口的距离为 c。那么环的长度 L b c。slow 从链表头走到相遇点一共走了 s a b。fast 从链表头走到相遇点它走的路程是 slow 的 2 倍同时因为 fast 比 slow 快它一定在环内多绕了至少一圈设多绕了 n 圈则 fast 走的路程是 2s a b n * L。把两个式子相减得到 s n * L也就是 a b n * L。把这个式子稍微变形a n * L - b (n - 1) * L (L - b) (n - 1) * L c也就是说链表头到环入口的距离 a等于相遇点绕环走 c 步再继续绕 n - 1 圈的距离。这个结论非常漂亮。它告诉我们在第一次相遇之后只要把一个指针放回链表头另一个指针留在相遇点两者都以步长 1 前进它们一定会在环入口处相遇。因为从 head 出发的指针走 a 步到达入口从相遇点出发的指针走 c (n-1)L 步也会绕回到入口。直观上更好理解的一种说法是假设两个指针在环内相遇时把 fast 当作已经多走了 nL的人。从相遇点往后走 c 步就能到环入口而从链表头走到环入口也正是 a 步这两个距离之间只差整数圈环长所以让两个指针同速前进第一步会在环入口相遇往后每走一圈也会在环入口相遇但第一次相遇必然发生在入口。4.3 为什么 slow 一定在环里走不到一圈就被追上还有个细节值得单独说。有些同学在推导时担心如果环很小而链表头到入口很远slow 进入环的时候fast 已经在环里绕了好多圈了那 slow 在环里会不会绕了好几圈才被追上第一次相遇时会不会已经超过一圈实际上不会。当 slow 刚进入环的入口时假设 fast 已经领先了 slow 若干距离。slow 走完一圈的时间里fast 会走两圈。fast 比 slow 多走的距离足够在 slow 还没走满一圈之前把它追上。所以第一次相遇时slow 在环内走的距离一定小于环长也就是 b L。这个性质保证了上面的推导中 c 是正数整个公式是自洽的。你可以拿一个具体例子验证。比如链表头到环入口距离 a 2环长度 L 4环入口之后依次是 1、2、3 号节点再回到入口。slow 走到入口需要 2 步此时 fast 已经走了 4 步它可能已经在环里绕了一圈且停在某个位置。之后 slow 在环内走fast 两步两步地追一定在 slow 绕完一圈内相遇。测试边界时建议额外测这几种情况空链表、单节点自环节点 next 指向自己、普通环、入口就在头节点、无环的普通链表。除了快慢指针这道题用哈希表也很容易解遍历所有节点把访问过的节点地址存到 unordered_set 里第一个重复出现的节点就是环入口。空间复杂度是 O(n)但理解起来非常直观。面试时可以先用哈希表解释思路再给出快慢指针的 O(1) 空间解法面试官通常会比较满意这个递进。5. 把四道题串起来链表操作的四板斧5.1 四个技巧到底在解决什么问题刷完这四道题最明显的感觉是它们每一道都在用不同的角度强调同一个核心——在单链表里想访问某个节点只能从头开始顺着 next 往后走所以要么用额外的指针记住位置要么用距离差抵消未知的长度。我对这四道题做了一个总结也欢迎大家用来做自己的复习索引题目核心技巧一句话本质24. 两两交换链表中的节点虚拟头节点 保存后继改链之前先记住下一步要去哪19. 删除链表的倒数第N个节点快慢指针距离差把倒数转换成距离差面试题 02.07. 链表相交长度差对齐 / 拼接链表消除两条链表的长度差142. 环形链表II快慢指针追及 数学推导用路程差反推环入口位置虚拟头节点解决的是头节点会变的通用问题双指针解决的是一次遍历完成定位的问题长度差对齐是在两条链表之间创造相同的起点环形链表的数学推导则是把追及问题的路程关系转化成可编程的指针移动。这四个技巧单独看都不难但组合起来几乎覆盖了链表题的大部分考法。比如很多中等难度的链表题本质就是虚拟头节点 快慢指针或者保存后继 数学推导的组合。5.2 我踩过的坑估计你也会踩在训练营里我在四道题上反复踩了下面几个坑特意记下来第一个坑是忘记保存后继节点。24 题交换节点时没有先把 tmp2 存下来就修改了 node1-next结果整个后半段链表丢了。这个错误非常隐蔽因为小链表测试用例可能碰巧没暴露问题但链表一长就崩。第二个坑是 while 条件里解引用空指针。19 题如果写成 while (fast ! NULL)fast 走到 NULL 后 fast-next 就是空指针访问。链表题对空指针极其敏感写循环前先想清楚 fast 最后停在哪个位置。第三个坑是 02.07 题用 val 相等判断相交。这个错在概念层面本质上是没有理解节点相交指的是地址相同。建议做链表题的时候始终在脑海里把每个节点想成内存里的一块区域而不是一个数字。第四个坑是 142 题只背代码不会推导。如果面试官追问为什么相遇点重新放一个指针、另一个指针从头出发就能在入口相遇背代码的人是答不上来的。宁可代码写得慢一点也要一步一步画出 a、b、c 三个距离之间的关系。5.3 刷完这四道题之后建议继续做三件事第一关掉所有题解在纸上画出四道题的链表变化过程。24 题画出交换三连19 题画出快慢指针的相对位置02.07 题画出两个指针走过的路径142 题画出相遇点和入口的位置关系。画完再写代码你会发现代码就是图的翻译。第二把每一题的暴力解法和最优解法都各写一遍。暴力解法不是为了提交而是用来对照最优解到底优化了什么。比如 19 题先写两遍遍历再写双指针02.07 题先写哈希表再写长度差142 题先写哈希表再写快慢指针。对比之下你才能真正记住优化的动机。第三整理一份属于自己的易错清单。这个清单不需要很长三五条就够但每一条都要具体到我在哪一题、哪一个步骤写错过。我自己的清单第一条就是凡是改动 next 指针之前先问一句原来这后面还有没有节点需要保留这句话救了我很多次。最后分享一点个人体会。练完第四天之后我发现自己拿到链表题不再急着写代码而是先在草稿纸上画节点、画箭头把操作顺序理清楚再动手。链表的题目看起来很考记忆力其实更考空间想象力。只要画图习惯养成了像 24 题这种看起来很绕的节点交换写起来也只是照图填代码而已。希望这篇总结能帮你在训练营第四天少走一点弯路。 链表题四板斧：虚拟头节点、双指针、长度差与快慢指针全掌握
如果你正在跟着代码随想录算法训练营打卡大概率会在第四天撞上这组题目LeetCode 24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07. 链表相交、142. 环形链表II。刷之前我觉得链表题无非就是把指针掰来掰去刷完之后我才意识到这四道题根本就是同一个主题的四个侧面——虚拟头节点怎么用、双指针怎么给链表定位、长度差怎么消除、追及问题怎么转化成数学公式。这篇文章我不打算把官方题解复述一遍而是从训练营学员最容易卡壳的地方切入把这四道题的设计意图和证明过程说清楚顺便整理一份可以直接复用的链表操作检查清单。非常适合正在跟着训练营打卡但被指针绕晕的学员也适合已经刷完一遍、想回头把链表底层套路系统整理一遍的朋友。1. 两两交换链表中的节点虚拟头节点才是整道题的灵魂1.1 为什么一上来就要造一个虚拟头节点先读题。给定 1 - 2 - 3 - 4要求返回 2 - 1 - 4 - 3。注意题目的限制条件不能只是单纯的改变节点内部的值也就是说必须真的去调整节点之间的 next 指向。我第一次写这道题时第一反应是直接从头节点开始交换。但很快发现一个尴尬的问题倒数第二个节点变成了新的头节点原来的 head 变量失效了后面所有逻辑都要针对头节点是否变化做特判。代码会写得又臭又长还容易漏。解决办法就是引入一个虚拟头节点 dummyHead让 dummyHead-next 永远指向真正的头节点。无论后面的节点怎么交换dummyHead 本身不发生移动最后直接返回 dummyHead-next 就是新链表。ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; // 后面逻辑 return dummyHead-next; }这里有一个很容易被忽略的好处dummyHead 让 cur 指针在遍历时始终指向一对待交换节点的前一个节点这样就不用区分当前操作的是不是头节点统一走同一套逻辑。这个思想在 19 题里还会再次出现。1.2 交换三连保存、重连、进位看图理解一下交换过程。假设当前状态是 dummyHead - node1 - node2 - nextPaircur 指向 dummyHead。我们要把 node1 和 node2 交换变成 dummyHead - node2 - node1 - nextPair然后 cur 前进到 node1继续处理下一对节点。我习惯用一个交换三连口诀先保存后继再改两条 next最后移动 cur。ListNode* tmp cur-next-next-next; // 保存 node2 之后的链表入口 cur-next cur-next-next; // 第 1 步指向 node2 cur-next-next tmp ? 原来的 node1 的位置 : nullptr; // 这一步需要先存 node1这里要特别小心上面这段代码是错的。因为在执行第 1 步之后原来的 node1 就被覆盖掉了必须提前保存。正确的写法是ListNode* tmp1 cur-next; // 保存 node1 ListNode* tmp2 cur-next-next-next; // 保存 node2 的下一个节点 cur-next cur-next-next; // cur 指向 node2 cur-next-next tmp1; // node2 指向 node1 tmp1-next tmp2; // node1 指向原来的后继 cur tmp1; // cur 移动tmp1 就是下一对节点的前驱这几行代码建议动手画图去理解而不是死背。我第一次没画图直接把 cur-next-next 改成了 node1结果后面半条链表直接丢了。链表题最大的特点就是这样只要有一条 next 指针没有正确接回去整条链就会断在某个地方。用生活化的例子来说这就好比排队的两个人要换位置。你先把排三以后的同学叫到一边站着tmp2然后让排二站到最前面排一站到排二后面最后把排三以后的同学重新拉回来接到队尾。只要有一环没接住队伍就散了。1.3 循环条件与奇数节点处理循环条件应该是 cur-next ! NULL cur-next-next ! NULL意思是当前待交换的一对节点必须都存在。如果链表节点数是奇数最后一个节点没有配对节点保持原样即可。很多新手会写成 while (cur-next ! NULL) 或者 while (cur ! NULL)这两种写法都会出问题。前者在只剩一个节点时cur-next-next 解引用空指针后者则会让 cur 直接走到链表末尾交换逻辑无法执行。建议用这几组测试用例自测空链表 []、单节点 [1]、双节点 [1,2]、三节点 [1,2,3]、四节点 [1,2,3,4]。尤其是奇数和偶数长度的链表都能跑通才说明循环边界没有问题。这道题的时间复杂度是 O(n)空间复杂度是 O(1)只使用了常数个临时指针变量。在训练营里这道题的通过率其实不算低但很多人是背下来的隔一天再写就卡住了。真正要掌握的是保存后继、重新接线、移动游标这个三件套。2. 删除链表的倒数第N个节点双指针的距离差才是关键2.1 先想清楚要删除的到底是哪个节点题目要求删除倒数第 N 个节点比如链表 1 - 2 - 3 - 4 - 5n 2删掉的是值为 4 的节点返回 1 - 2 - 3 - 5。最朴素的想法是两次遍历第一次算出链表的长度 len第二次走到第 len - n 个节点也就是待删除节点的前一个节点然后执行删除操作。这种方法当然能过但题目下面有一行进阶要求尝试使用一趟扫描实现。很多同学卡住是因为没有意识到一个关键点删除一个节点真正需要操作的是它的前驱节点。所以删除倒数第 N 个节点本质上等价于找到倒数第 N 1 个节点。只要能一次遍历定位到倒数第 N 1 个节点删除操作就顺理成章了。2.2 快慢指针怎么走距离差这里就是双指针登场的时候了。想象一个场景跑步比赛快的人先出了起跑线慢的人还在原地。如果快的人先跑出 N 1 步之后两个人以完全相同的速度前进那么当快的人到达终点时慢的人距离终点正好还有 N 1 步。放在链表场景里终点是 NULL慢的人刚好停在倒数第 N 1 个节点上。实现上通常会配合虚拟头节点。fast 和 slow 都从 dummyHead 出发fast 先走 n 步然后两个指针同步移动直到 fast-next NULL。此时 slow 正好指向倒数第 N 1 个节点。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; while (n-- fast ! NULL) { fast fast-next; } while (fast-next ! NULL) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummyHead-next; }注意这里 fast 只先走了 n 步而不是 n 1 步。原因是循环条件是 fast-next ! NULL它等价于让 fast 走到最后一个有效节点时停止。此时 slow 正好在待删节点的前驱位置。如果你让 fast 先走 n 1 步那循环条件就得改成 fast ! NULL两者的本质是一样的不要记混。我见过不少同学在这里纠结为什么不是 fast 先走 n 步、然后 fast 和 slow 一起走、fast 为 NULL 时 slow 正好是倒数第 N 个节点这样确实定位到了目标节点本身但单链表无法直接删除当前节点除非再多维护一个前驱指针复杂度反而更高了。2.3 虚拟头节点的作用在这里更明显如果没有 dummyHead删除头节点 return head-next 需要单独处理。加入 dummyHead 之后fast 和 slow 都从 dummyHead 出发哪怕要删除的就是原链表的头节点slow 依然能指向它的前驱dummyHead不需要任何特判。这道题还有一个延伸考点如果不用双指针能不能用递归或栈实现可以。递归回溯的时候计数或者把节点全部压入栈弹出第 N 个删除都能做。但栈会引入 O(n) 的额外空间双指针是面试官最想听到的解法。边界测试建议覆盖单节点链表 n1、链表长度等于 n删头节点、链表长度为 n1删末尾节点、n 大于链表长度题目通常保证 n 有效但要心里有数。我在训练营里看到很多同学写这道题时一上来就求长度看到题目的进阶提示又不敢用双指针。其实双指针的本质就是把这个长度差提前算好利用两个指针之间的相对距离来确定位置。一旦理解了它是怎么消除第二次遍历的19 题基本不会忘。3. 链表相交长度差就是破局点3.1 相交的不是节点值是节点本身面试题 02.07 的表述很有意思给你两个单链表的头节点 headA 和 headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null。题目很阴险的一个细节是示例里的链表值是 4、1、8、4、5 和 5、0、1、8、4、5其中都出现了值为 1 和值为 8 的节点。很多人第一次做这道题会把节点值相等当成节点相交然后发现怎么都跑不对。链表相交的本质是指针地址相同。两个节点指向内存里的同一个对象它们的 val 当然相同但 val 相同不代表它们是同一个节点。举个例子链表达成 A 是 [1,9,1,2,4]B 是 [3,2,4]第一个共同的节点是值为 2 的那个节点而不是值为 1 的节点因为 A 里的 1 和 B 里的 1 不是同一个节点。想明白这一点后这道题的一切解法都建立在两个指针指向同一个地址这个判断上。3.2 解法一先把长的链表走掉差值再同步比较假设两条链表相交那么从交点开始它们后面部分的长度是完全相同的。所以如果在交点之前两条链表的长度不同只需要让较长的那条链表先走几个节点把长度差补平然后两条链表的指针保持同步前进第一个相同地址的节点就是交点。第一步求两条链表的长度第二步让长的先走 gap 步第三步同步遍历。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* curA headA; ListNode* curB headB; int lenA 0, lenB 0; while (curA ! NULL) { lenA; curA curA-next; } while (curB ! NULL) { lenB; curB curB-next; } curA headA; curB headB; if (lenB lenA) { swap(lenA, lenB); swap(curA, curB); } int gap lenA - lenB; while (gap--) { curA curA-next; } while (curA ! NULL curB ! NULL) { if (curA curB) return curA; curA curA-next; curB curB-next; } return NULL; }交换变量那一步是为了保证 curA 永远指向较长链表的头节点这样后面只需要一个 gap 变量就能统一处理不用写两套逻辑。这个习惯在写代码时可以经常用能省掉不少分支判断。3.3 解法二走完自己的路再去走别人的路第二种解法不需要求长度代码也短得多ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA NULL ? headB : pA-next; pB pB NULL ? headA : pB-next; } return pA; }核心思路是把 pA 想象成在走链表达成 链表 B这条路径pB 想象成在走链表 B 链表 A这条路径。两条路径的总长度完全相等如果两条链表相交pA 和 pB 必然在交点相遇如果不想交它们最终会同时走到 NULL退出循环并返回 NULL。为什么一定会在交点相遇设链表达成独立部分的长度为 a链表 B 独立部分的长度为 b公共部分的长度为 c。pA 走到交点需要经过 a c再走到链表 B 的末尾需要经过 bpB 走到交点需要经过 b c再走到链表达成的末尾需要经过 a。两者走的总距离都是 a b c所以在走过自己那条链表、再走对方独立部分时必然在同一个位置碰到。很多同学一开始不理解这个解法会觉得 pA 和 pB 怎么可能在不同长度链表上走到同一个节点。其实这就是把两条链表尾部对齐之后在起点处比较的一个变形。当 pA 走完链表达成就接着走链表 B 的头部相当于人为地把两条链表拼接成了 AB 和 BA它们共享同一个尾部交点之后的部分所以最后一段路是同步的。面试时如果让我推荐我会先说长度差对齐的解法因为它更好解释再补充一遍拼接解法展示自己知道更简洁的版本。两道题的代码都不长但要能画出两种思路的推导过程才算真正掌握。4. 环形链表II快慢指针以及那个绕不开的数学推导4.1 先判断有没有环快指针一次跳两步142 题是四道题里推导最重的一道也是训练营里讨论度最高的题之一。题目要求判断链表是否有环如果有返回环的入口节点。判断有没有环最经典的做法是快慢指针slow 每次走一步fast 每次走两步。如果链表里有环fast 迟早会在环里追上 slow因为它们进入环之后一个快一个慢运行轨迹是闭合的。这里经常有人问为什么快指针要一次走两步不能走三步吗理论上快指针一次走三步也可能追上但可能不够可靠因为当 slow 和 fast 都在环内运动时如果步长是 3存在一种情况是 fast 一次性跨过 slow导致它们永远错开。步长 2 时每经历一个时间单位fast 相对 slow 接近一步由于环是有限的闭环一定能追上。实现时要注意一个细节fast 每次跳两步前必须确认 fast ! NULL 且 fast-next ! NULL否则会空指针异常。这也是 while 循环条件的来源。ListNode* detectCycle(ListNode* head) { ListNode* fast head; ListNode* slow head; while (fast ! NULL fast-next ! NULL) { 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 NULL; }4.2 找入口的数学推导从相遇点出发再走一段就能到入口假设链表头到环入口的距离为 a环入口到快慢指针第一次相遇点的距离为 b相遇点继续沿着环走回环入口的距离为 c。那么环的长度 L b c。slow 从链表头走到相遇点一共走了 s a b。fast 从链表头走到相遇点它走的路程是 slow 的 2 倍同时因为 fast 比 slow 快它一定在环内多绕了至少一圈设多绕了 n 圈则 fast 走的路程是 2s a b n * L。把两个式子相减得到 s n * L也就是 a b n * L。把这个式子稍微变形a n * L - b (n - 1) * L (L - b) (n - 1) * L c也就是说链表头到环入口的距离 a等于相遇点绕环走 c 步再继续绕 n - 1 圈的距离。这个结论非常漂亮。它告诉我们在第一次相遇之后只要把一个指针放回链表头另一个指针留在相遇点两者都以步长 1 前进它们一定会在环入口处相遇。因为从 head 出发的指针走 a 步到达入口从相遇点出发的指针走 c (n-1)L 步也会绕回到入口。直观上更好理解的一种说法是假设两个指针在环内相遇时把 fast 当作已经多走了 nL的人。从相遇点往后走 c 步就能到环入口而从链表头走到环入口也正是 a 步这两个距离之间只差整数圈环长所以让两个指针同速前进第一步会在环入口相遇往后每走一圈也会在环入口相遇但第一次相遇必然发生在入口。4.3 为什么 slow 一定在环里走不到一圈就被追上还有个细节值得单独说。有些同学在推导时担心如果环很小而链表头到入口很远slow 进入环的时候fast 已经在环里绕了好多圈了那 slow 在环里会不会绕了好几圈才被追上第一次相遇时会不会已经超过一圈实际上不会。当 slow 刚进入环的入口时假设 fast 已经领先了 slow 若干距离。slow 走完一圈的时间里fast 会走两圈。fast 比 slow 多走的距离足够在 slow 还没走满一圈之前把它追上。所以第一次相遇时slow 在环内走的距离一定小于环长也就是 b L。这个性质保证了上面的推导中 c 是正数整个公式是自洽的。你可以拿一个具体例子验证。比如链表头到环入口距离 a 2环长度 L 4环入口之后依次是 1、2、3 号节点再回到入口。slow 走到入口需要 2 步此时 fast 已经走了 4 步它可能已经在环里绕了一圈且停在某个位置。之后 slow 在环内走fast 两步两步地追一定在 slow 绕完一圈内相遇。测试边界时建议额外测这几种情况空链表、单节点自环节点 next 指向自己、普通环、入口就在头节点、无环的普通链表。除了快慢指针这道题用哈希表也很容易解遍历所有节点把访问过的节点地址存到 unordered_set 里第一个重复出现的节点就是环入口。空间复杂度是 O(n)但理解起来非常直观。面试时可以先用哈希表解释思路再给出快慢指针的 O(1) 空间解法面试官通常会比较满意这个递进。5. 把四道题串起来链表操作的四板斧5.1 四个技巧到底在解决什么问题刷完这四道题最明显的感觉是它们每一道都在用不同的角度强调同一个核心——在单链表里想访问某个节点只能从头开始顺着 next 往后走所以要么用额外的指针记住位置要么用距离差抵消未知的长度。我对这四道题做了一个总结也欢迎大家用来做自己的复习索引题目核心技巧一句话本质24. 两两交换链表中的节点虚拟头节点 保存后继改链之前先记住下一步要去哪19. 删除链表的倒数第N个节点快慢指针距离差把倒数转换成距离差面试题 02.07. 链表相交长度差对齐 / 拼接链表消除两条链表的长度差142. 环形链表II快慢指针追及 数学推导用路程差反推环入口位置虚拟头节点解决的是头节点会变的通用问题双指针解决的是一次遍历完成定位的问题长度差对齐是在两条链表之间创造相同的起点环形链表的数学推导则是把追及问题的路程关系转化成可编程的指针移动。这四个技巧单独看都不难但组合起来几乎覆盖了链表题的大部分考法。比如很多中等难度的链表题本质就是虚拟头节点 快慢指针或者保存后继 数学推导的组合。5.2 我踩过的坑估计你也会踩在训练营里我在四道题上反复踩了下面几个坑特意记下来第一个坑是忘记保存后继节点。24 题交换节点时没有先把 tmp2 存下来就修改了 node1-next结果整个后半段链表丢了。这个错误非常隐蔽因为小链表测试用例可能碰巧没暴露问题但链表一长就崩。第二个坑是 while 条件里解引用空指针。19 题如果写成 while (fast ! NULL)fast 走到 NULL 后 fast-next 就是空指针访问。链表题对空指针极其敏感写循环前先想清楚 fast 最后停在哪个位置。第三个坑是 02.07 题用 val 相等判断相交。这个错在概念层面本质上是没有理解节点相交指的是地址相同。建议做链表题的时候始终在脑海里把每个节点想成内存里的一块区域而不是一个数字。第四个坑是 142 题只背代码不会推导。如果面试官追问为什么相遇点重新放一个指针、另一个指针从头出发就能在入口相遇背代码的人是答不上来的。宁可代码写得慢一点也要一步一步画出 a、b、c 三个距离之间的关系。5.3 刷完这四道题之后建议继续做三件事第一关掉所有题解在纸上画出四道题的链表变化过程。24 题画出交换三连19 题画出快慢指针的相对位置02.07 题画出两个指针走过的路径142 题画出相遇点和入口的位置关系。画完再写代码你会发现代码就是图的翻译。第二把每一题的暴力解法和最优解法都各写一遍。暴力解法不是为了提交而是用来对照最优解到底优化了什么。比如 19 题先写两遍遍历再写双指针02.07 题先写哈希表再写长度差142 题先写哈希表再写快慢指针。对比之下你才能真正记住优化的动机。第三整理一份属于自己的易错清单。这个清单不需要很长三五条就够但每一条都要具体到我在哪一题、哪一个步骤写错过。我自己的清单第一条就是凡是改动 next 指针之前先问一句原来这后面还有没有节点需要保留这句话救了我很多次。最后分享一点个人体会。练完第四天之后我发现自己拿到链表题不再急着写代码而是先在草稿纸上画节点、画箭头把操作顺序理清楚再动手。链表的题目看起来很考记忆力其实更考空间想象力。只要画图习惯养成了像 24 题这种看起来很绕的节点交换写起来也只是照图填代码而已。希望这篇总结能帮你在训练营第四天少走一点弯路。