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