【算法】链表二链表上的双指针——变速、异链与定距和一份路程账本摘要链表系列第二篇。数组转场链表时我说快慢指针做过——做到 LC19 才发现链表上的双指针是另一个世界数组指针是下标可以回头看链表指针是节点地址改了就丢于是双指针在链表上长出了三种新形态。本篇四题LC141 环形链表变速双指针——快 2 慢 1 的恒定节拍快走 3 步行不行的奇偶性论证以及 Val 比较误报的教训——有环的判定是同一个节点被再次到达认点不认值LC142 环形链表 II四版弧线——先判后动的初始同点、两段判定顺序必须相反、a ≡ c (mod 环长)的路程账本、调试器实证三个变量同地址的误诊事件、以及一个无意中造出的 a0 杀局LC160 相交链表异链双指针——跳链补路程、nil 也会师、以及指针一轮一动一格纪律的两件新马甲瞬移和冻结LC19 删倒数第 N定距双指针——倒数第 n ⟺ 与终点距离 n的转化、两套等价账的对照。收尾把三题的数学合账a≡c 和 acb bca 是同一族——都是在时间轴上凑出相等的路程。前置阅读链表一世界观与指针操作——攥住再改、重绑与改对象、哨兵节点。配套代码仓库按题号分目录https://github.com/a18792721831/studyleetCode【算法】链表二链表上的双指针——变速、异链与定距和一份路程账本【算法】链表二链表上的双指针——变速、异链与定距和一份路程账本摘要0. 链表双指针的四形态总览1. 第一课 LC141变速双指针与奇偶性2. 第二课 LC142四版弧线与 a≡c 账本3. 第三课 LC160异链双指针与 nil 会师4. 第四课 LC19定距双指针5. 三题合账路程数学的一族6. 速查表总结参考资料0. 链表双指针的四形态总览形态指针关系代表题核心机制同向prev/curr 一前一后LC206 反转攥住再改、单向推进变速快 2 慢 1 同起点LC141/142 找环速度差1、路程账本异链pA/pB 各走一条、到头互跳LC160 相交跳链补路程、nil 会师定距fast/slow 固定间距 nLC19 删倒数间距保持、终点代打数组的双指针比的是下标怎么动链表的双指针比的是路程怎么凑——因为链表没有绝对位置一切判定都落在谁比谁多走了多少上。这篇的主线就是一本路程账。1. 第一课 LC141变速双指针与奇偶性判断链表是否有环O(1) 空间。第一反应是哈希表记走过的节点“不记就无法感知重复”——错了必须记录是可以攻破的断言。操场跑圈的直觉你不需要记住跑过哪些位置只需要一个比你快的人——他迟早从背后撞上你。感知在转圈不需要记忆只需要速度差。slow,fast:head,headforfast!nilfast.Next!nil{// 快指针跳两步的两级守卫slowslow.Next// 慢每轮 1 步fastfast.Next.Next// 快每轮 2 步ifslowfast{// 指针比较不是 Valreturntrue}}returnfalse三份判决书一份比一份深判决书一一定相遇两指针都进环后设环上距离 d每轮慢 1、快 2 ⟹d 恰减 1——整数逐级递减必到 0。判决书二不会跳过距离从 2→1→0 逐级归零不会从 2 直接越过 0。判决书三为什么是快 2 慢 1不能快 3 慢 1速度差 2 ⟹ 距离每轮 -2 ⟹奇偶性不变——初始距离是奇数就永远差 1 错开永不相遇。速度差 1 是唯一保证距离逐级归零的配比。这是面试追问的常客也是随手配置和理解配置的分界线。两个工程教训同样值钱Val 比较是本质错误[1,1]无环但两节点同值误报——有环的判定是同一个节点被再次到达认点不认值节点地址唯一守卫必须两级快指针一次跳两步跳之前必须确认两步都踩得到地——fast ! nil fast.Next ! nil这是改指针前先攥住的空指针版。还有命名纪律我交的版本 f 走一步、s 走两步——名字和速度倒置功能全对但半年后重读必先理解反。变量名不换含义。2. 第二课 LC142四版弧线与 a≡c 账本找到入环的第一个节点。判定部分同 141灵魂在相遇之后。算法相遇后一个指针回到 head、两指针同速齐走每次一步再次相遇的位置就是入环点。凭什么是它——本篇账本的核心a 头 → 入环点A 独有段 b 入环点 → 相遇点 c 相遇点 → 绕回入环点环长 b c slow 走了 a b fast 走了 a b n(bc) ← 套了 n 圈 fast 2 × slow a b n(bc) 2(ab) ⟹ a (n-1)(bc) c ⟹ a ≡ c (mod 环长) 解读从 head 走 a 步到入环点从【相遇点】走 c 步绕 n-1 圈也到入环点 ⟹ 同速齐走必然【同时】踏进入环点——会师于入环点拿[3,2,0,-4] pos1代数字最直观a1、b2、c1环长 3。第一段相遇在 -4slow 走 3 步、fast 走 6 步2×3第二段 head3 走 1 步到 2、slow-4 走 1 步也到 2——同时到达入环点。四版弧线各有一课v1先判后动。if fast slow写在移动之前——初始两指针天然同点都从 head 出发第一轮就 break。出发时的同点不是相遇——相遇的定义是各自走了若干步之后再次同点。判定必须在移动之后。v2两段判定顺序必须相反。第一段先动后判防起点同点被误判为相遇第二段先判后动防答案即起点被迈过——a0 时头就是入环点先动一步就把脚下的答案迈过去了。同一段代码两段判定顺序相反各有各的判决书。每个判定位置都要能说出为什么在这儿。v3调试器实证与一场误诊。我在断点里看到 fast/slow/head三个变量同地址第一反应是代码有 bug教练还误诊成你删了某行——真相是我 main 里把入环点当头传了进去a0 caseslow 走一整圈、fast 走两圈回到起点相遇——相遇点起点三者同地址是完全合法的状态。教训两条测试用例传错参数会制造看起来像 bug 的合法状态怀疑假设就断点看地址但看之前先把输入是什么搞对。v4无环短路。第一段自然退出fast 撞 nil后必须判无环再进第二段——否则 slow 停在链中间、齐走时 slow 先到 nilslow slow.Next解引用空指针。我用的if fast ! slow { return nil }比标准的fast nil || fast.Next nil更紧凑代价是隐含依赖多个守卫的合力空链、单节点靠第二段守卫兜底——能用但标准写法每行独立成立重读时不依赖合力推理。工程取舍知道即可。3. 第三课 LC160异链双指针与 nil 会师找两条链的交点同一个节点不是值相等。O(n) 时间 O(1) 空间。浪漫解法pA 从 headA 出发、走到 nil跳到 headBpB 对称。两指针在交点会师。判决书pA 总路程 a c b 走完 A跳过去把 B 的独有段补上 pB 总路程 b c a 两式恒等 ⟹ 同速前进必然同时到达交点跳链的本质只走自己的链pA 差 b、pB 差 a——跳链就是把对方的独有段补进自己的路程强行拉平。这和 LC142 的账本是亲缘那边靠快指针多绕圈补路程差这边靠跳到对方链上补——本质都是在时间轴上凑出相等的总路程。两个杀手边界nil 也会师不相交c0时pA 走 ab 步、pB 走 ba 步——同时到达 nil而nil nil是合法的指针比较for pA ! pB在那一刻自然变假返回 nil。相交返回交点、不相交返回 nil塞进同一个循环零特判。a0 或 b0对方链的头就是交点——它是一个货真价实的候选节点瞬移越过它漏判。这题我写了三版每版都是指针一轮一动一格纪律的新马甲v1 瞬移跳链之后又走了 .Next —— 从 nil 瞬移到 headB.Next b0 时跳过交点跳到 headB 是【抵达】不是【途经】 v2 冻结else if 链让 pAnil 时 pB 被冻结本该前进—— A 空时 pA 跳到 headB 撞上被冻结的 pB假会师 v3 独立窗口两个独立的 if-else每个指针自己决定跳还是走v2 的死因值得展开else if 是排队的窗口前面的命中后面的就不判但 pA 和 pB 的节奏语义上互不依赖——pA 是 nil 不该影响 pB 前进。语义独立的判定结构上也必须独立。非空用例全活、只有空链翻车是因为两指针到 nil 的时刻通常错开、冻结的副作用被掩盖——边界用例是唯一能暴露时序问题的探针。4. 第四课 LC19定距双指针删除链表倒数第 n 个节点一遍扫描。我最初把快慢指针锁死在 141 的变速追赶模型上想成环上相遇卡住——LC19 是第四形态定距。钥匙是一句话转化倒数第 n 个 ⟺ 与终点的距离恰好是 n。不需要知道链长 L那要两遍扫描——派 fast 替你踩终点slow 与它保持 n 的间距dummy:ListNode{}// 删头节点没有前驱——dummy 挡在前面dummy.Nexthead fast,slow:dummy,dummyfori:0;in;i{// fast 先走拉开间距fastfast.Next}forfast.Next!nil{// 同速齐走fast 停在尾节点fastfast.Next slowslow.Next}slow.Nextslow.Next.Next// slow 停在被删节点的【前驱】returndummy.Next两个细节各值一行注释fast 停在尾节点fast.Next ! nil为界还是 nil两套账等价先走停止条件slow 终点标准版n1 步fast nil倒数第 n1前驱我的版n 步fast.Next nil停在尾倒数第 n1前驱我的 fast 两头各省一格净效果 slow 停在同一位置——殊途同归但注释必须配自己的实现我注释里写slow 到倒数第 n 个就是记了标准版的结论配自己的算法差的那格恰好被实现细节补掉——账面和实现脱节重读必困惑。为什么 slow 要停在前驱而不是被删节点上单向链表删节点是slow.Next slow.Next.Next——没有 prev 指针删除永远需要前驱。这是链表公理二没有回头看的直接推论也是为什么 slow 的设计目标是倒数第 n1而不是倒数第 n。5. 三题合账路程数学的一族题等式补差手段LC142a ≡ c (mod 环长)fast 走 abn(bc) 2×(ab)快指针多绕圈LC160acb bca走完自己跳对方链LC19fast 路程 − slow 路程 ≡ n恒定fast 先走 n 步三道题的判决书是同一个模板两个指针各自的路程列个等式等式保证同速必会师/间距必保持。链表双指针的深度不在指针操作那是第一篇的事在这本账——写代码前先把等式列出来代码就是等式的翻译。6. 速查表问题判据/口诀出处感知环不需要记忆需要速度差快 2 慢 1速度差 1 是唯一逐级归零的配比差 2 奇偶性锁死LC141环判定比较什么指针同一个节点不是 Val值可重复LC141快指针守卫一次跳两步先判两级非 nilLC141判定位置先动后判 or 先判后动——取决于防起点同点还是防答案即起点LC142/LC160入环点a ≡ c (mod 环长)相遇后一头一回 head同速齐走会师于入环点LC142异链找交点走完自己跳对方acb bcanil 也会师不相交自动返回 nilLC160跳链语义跳到对方头是抵达不是途经对方头可能是交点跳链轮不前进LC160语义独立的判定结构上也必须独立两个 if-else不是一条 else if 链LC160 v2倒数第 n⟺ 与终点距离 nfast 先拉开 n、同速齐走、slow 停前驱LC19删除节点永远需要前驱无 prev 指针——dummy 补上头的前驱LC19注释纪律结论必须配自己的实现两套等价账别记混LC19调试器怀疑指针假设 → 断点看地址但先确认输入传对了LC142总结四题十二版141 两版、142 四版、160 三版、19 一版加一轮卡壳链表双指针的四种形态全部过手。三个感想链表双指针的本质是路程账不是指针戏法。四形态同向/变速/异链/定距的判定书全部落在两个指针的路程列等式上——a≡c、acbbca、路程差恒为 n。写代码前先列等式等式对了代码就是翻译等式没列就动笔四版起步142 和 160 的弧线都是证据。指针一轮一动一格是我最难戒的病。双指针系列四件马甲平行 if、递归多路链表又添两件瞬移跳链后又 .Next越过候选节点冻结else if 让无辜的指针停摆。六件马甲一个病根想让一轮做超过一格的事。纪律倒是一句话每轮每个指针恰好一个动作——要么前进要么跳链抵达没有第三种。边界用例是时序问题的唯一探针。a0头即入环点/交点、空链、单节点——这些输入逼迫两个指针在同一轮发生罕见的事件组合同时到 nil、起点即答案把节奏错误当场引爆。非空、a0 的常规用例会把冻结、瞬移这些 bug 掩盖到天荒地老——测试用例的优先级永远是上次死过的形状优先。链表系列两篇收官。下一站按路线图堆与单调栈接 LC862 的前缀和单调队列伏笔或按需调整。参考资料LeetCode 141. 环形链表LeetCode 142. 环形链表 IILeetCode 160. 相交链表LeetCode 19. 删除链表的倒数第 N 个结点LeetCode 206. 反转链表链表一世界观与指针操作——攥住再改、重绑与改对象、哨兵节点双指针与滑动窗口一框架总纲——三类问题、一个原理与判决书版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。