02.3.1.2 相交、环检测与快慢指针
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表
02.3.1.2-001 快慢指针为什么能用于链表问题?
一句话结论
快慢指针以不同速度沿链表前进,利用速度差在有限步数内产生确定的相对位置关系:快针到尾定位中点,环内快针必然追上慢针,是 O(n) 时间 O(1) 空间的核心技巧。
概念解释
- 速度:slow 一步,fast 两步。
- 相对运动:环内速度差一步,必然相遇。
- 线性链:快针先到尾,慢针在半程。
原理流程
- 两指针同起点。
- 按速度推进。
- 依据终止条件读取位置关系。
代码 / 图示
线性:fast 到 null → slow 中点
环形:fast 绕圈追上 slow → 相遇
常见误区
- 误区:快慢指针只用于找环;正解:中点、倒数节点也用。
- 误区:快针速度必须固定 2;正解:2 步便于保证环内必相遇,其他速度需另证。
追问
- Q:快慢指针空间复杂度? A:O(1),两个指针变量。
- Q:两指针起点不同可以吗? A:可以,按问题设定间距(如倒数 N 步)。
02.3.1.2-002 判断链表是否有环(LC 141)怎么做?
一句话结论
快慢指针同起点,fast 两步、slow 一步;相遇即有环,fast 到 null 则无环;O(n) 时间 O(1) 空间。
概念解释
- 无环:快针先到尾部 null。
- 有环:快针在环内追上慢针。
- 相遇:指针相等(同一节点)。
原理流程
- slow=fast=head。
- fast 两步,slow 一步。
- 相等返回 true;fast 不可继续返回 false。
代码 / 示例
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
常见误区
- 误区:用哈希表判环才标准;正解:快慢指针空间更优。
- 误区:循环条件只判 fast;正解:fast.next 可能为 null。
追问
- Q:环长 1(自环)能检测吗? A:能,fast 两步回到同节点相遇。
- Q:相遇一定是环内节点吗? A:是,无环不会相遇。
02.3.1.2-003 找环入口(LC 142)怎么做?
一句话结论
快慢相遇后,把一个指针放回 head,两指针同速前进,再次相遇节点即环入口;O(n) 时间 O(1) 空间。
概念解释
- 第一次相遇:环内追及。
- 二次同速:定位入口。
- 数学关系保证相遇点为入口。
原理流程
- 快慢相遇。
- p=head,slow 留在相遇点。
- 同速一步前进。
- 再次相等即入口。
代码 / 示例
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}
常见误区
- 误区:相遇点就是入口;正解:相遇点在环内,需二次同速找入口。
- 误区:二次指针从 null 出发;正解:一个回 head,一个留相遇点。
追问
- Q:无环时返回什么? A:null。
- Q:入口就是 head? A:二次同速立即在 head 相遇,正确。
02.3.1.2-004 环入口结论的数学推导是什么?
一句话结论
设头到入口距离 a,入口到相遇点 b,相遇点回入口 c;慢针走 a+b,快针走 a+b+n(b+c);由快针路程两倍慢针得 a = n(b+c)-b,即 a = (n-1)(b+c)+c,所以从 head 走 a 步与从相遇点绕 (n-1) 圈再加 c 步同时到入口。
概念解释
- 路程关系:快 = 2 × 慢。
- 环周长:b+c。
- 入口距离:a。
原理流程
- 标注 a、b、c 与圈数 n。
- 列快慢路程方程。
- 化简得 a 与 c 的关系。
代码 / 图示
head —a→ 入口 —b→ 相遇点
相遇点 —c→ 入口(环长 b+c)
2(a+b) = a+b+n(b+c)
→ a = (n-1)(b+c) + c
常见误区
- 误区:推导依赖快针只多走一圈;正解:多圈同样成立,n 为任意圈数。
- 误区:b、c 方向定义混乱;正解:先画图标注方向再列方程。
追问
- Q:n 一定等于 1 吗? A:不一定,快针可能绕多圈,结论仍成立。
- Q:哈希表法找入口? A:记录访问过的节点,第一次重复即入口,O(n) 空间。
02.3.1.2-005 为什么快指针走两步而不是三步?
一句话结论
两步速度差为 1,环内每轮逼近一格,必然在环内相遇不跳过;三步速度差 2,偶数环可能出现追逐错位、永不相遇,证明更复杂,工程上选两步最稳。
概念解释
- 速度差 1:相邻格逼近。
- 模环长:差与环长不互素可能错位。
- 两步证明简单、实现通用。
原理流程
- 环内位置按模环长变化。
- 速度差与环长决定是否相遇。
- 两步保证差 1,必相遇。
代码 / 图示
差 1:每轮距离减 1,必追上
差 2:环长偶数时差保持偶数,可能擦肩而过
常见误区
- 误区:快针越快越好;正解:速度差过大可能错过相遇。
- 误区:三步也一定相遇;正解:需按环长与差互素性分析。
追问
- Q:快针走三步能检测环吗? A:多数情况可,但相遇证明不如两步稳妥,面试默认两步。
- Q:相遇判断用值还是引用? A:引用相等
==,不是值相等。
02.3.1.2-006 环的长度怎么求?
一句话结论
快慢相遇后,从相遇点出发单针绕环一圈回到原点,计数即环长;O(环长) 时间 O(1) 空间。
概念解释
- 相遇点在环内。
- 绕圈一周回到同点。
- 步数即周长。
原理流程
- 第一次相遇。
- 单针从相遇点走,计数。
- 回到相遇点停止。
代码 / 示例
int cycleLength(ListNode meet) {
int len = 0;
ListNode cur = meet;
do { cur = cur.next; len++; } while (cur != meet);
return len;
}
常见误区
- 误区:从头开始数到相遇点;正解:那段含环外距离,不是环长。
- 误区:先判空再绕圈;正解:无环不存在相遇点。
追问
- Q:已知入口求环长? A:从入口绕一圈计数。
- Q:环长与入口距离独立吗? A:独立,分别测量。
02.3.1.2-007 相交链表(LC 160)怎么找交点?
一句话结论
两指针分别遍历两条链,走到尾部后换到另一链头继续;相遇点即交点;两链路程都等于 a + 公共 + b,路径长度拉平;O(m+n) 时间 O(1) 空间。
概念解释
- 相交:交点之后尾部共享。
- 换头:消除长度差。
- 同时到达交点。
原理流程
- pA、pB 从两头出发。
- 到尾后换到另一链头。
- 相遇即交点;都为 null 则不相交。
代码 / 示例
public ListNode getIntersectionNode(ListNode a, ListNode b) {
ListNode p = a, q = b;
while (p != q) {
p = p != null ? p.next : b;
q = q != null ? q.next : a;
}
return p;
}
常见误区
- 误区:比较值相等判断交点;正解:必须引用相等。
- 误区:不相交时换头会死循环;正解:两针最终同时为 null 退出。
追问
- Q:为什么换头后会相遇? A:各自走过 独有段 + 公共段 + 对方独有段,总路程相同。
- Q:有交点但长度相等? A:同速遍历,在交点自然相遇。
02.3.1.2-008 相交链表的长度差消除法怎么做?
一句话结论
分别求两链长度,长链先走差值步,再同速前进,首次引用相等即交点;O(m+n) 时间 O(1) 空间,思路直观。
概念解释
- 长度差在独有段。
- 先走差值对齐尾部。
- 同速扫描找共享节点。
原理流程
- 求 lenA、lenB。
- 长链先走差值。
- 同速比较引用。
代码 / 示例
int la = length(a), lb = length(b);
ListNode p = a, q = b;
while (la > lb) { p = p.next; la--; }
while (lb > la) { q = q.next; lb--; }
while (p != q) { p = p.next; q = q.next; }
return p;
常见误区
- 误区:比较值判断相交;正解:引用相同才是同一节点。
- 误区:差值步走错链;正解:长链先起步。
追问
- Q:两种方法哪个好? A:换头法省去求长度,代码更短;长度差法更易解释。
- Q:不相交返回什么? A:null。
02.3.1.2-009 哈希表法判相交/判环怎么做?
一句话结论
遍历一条链把节点存入集合,再遍历另一条查集合;判环同理记录访问节点,重复出现即环;O(n) 时间 O(n) 空间,作为双指针的对照方案。
概念解释
- 集合存引用。
- 第二次出现即重复。
- 空间换直观。
原理流程
- 第一遍存节点。
- 第二遍查存在性。
- 命中即交点/环点。
代码 / 示例
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (!seen.add(head)) return head; // 环
head = head.next;
}
常见误区
- 误区:集合存节点值;正解:存节点引用,值重复不等于同一节点。
- 误区:哈希法空间 O(1);正解:O(n)。
追问
- Q:什么场景用哈希法? A:需要记录路径、双指针不适用时。
- Q:判环哈希法一定正确吗? A:正确,只是空间更高。
02.3.1.2-010 有环链表与相交链表有什么区别?
一句话结论
相交是两条链共享一段尾部(无环前提下);有环是一条链自身首尾成环;相交可能发生在环上,题目通常先假设无环再判相交。
概念解释
- 相交:节点引用相同。
- 环:next 指回前面节点。
- 复合场景:两链在环上相交需单独讨论。
原理流程
- 先判断是否有环。
- 无环再按相交方法处理。
- 有环相交分交点在环外/环内。
代码 / 图示
无环相交:a 尾接 b 中段
有 环:自身 next 回指
常见误区
- 误区:相交链表可能有环;正解:标准题设为无环链表。
- 误区:两条链值相同即相交;正解:引用相同才共享节点。
追问
- Q:两带环链表相交怎么判? A:先各自判环与入口,再比较环是否相同,属进阶题。
- Q:相交后能否分开? A:结构上共享尾部,改动会影响两条链。
02.3.1.2-011 环内追及为什么一定相遇?
一句话结论
进入环后,快针每轮比慢针多走一格,两者距离沿环递减;有限环长内距离必然归零,即相遇;前提是速度差与环长兼容。
概念解释
- 环内位置模周长。
- 速度差 1 逐格逼近。
- 有限步内追上。
原理流程
- 两针都进入环。
- 每轮距离减 1。
- 距离为 0 相遇。
代码 / 图示
环长 L,距离 d
每轮 d → d-1(模 L)
d=0 相遇
常见误区
- 误区:快针超过慢针就错过;正解:差 1 时相邻步进必然落在同点。
- 误区:环外阶段也算追及;正解:追及发生在都进入环之后。
追问
- Q:慢针还没进环快针已经绕圈? A:不影响,进环后仍按差 1 逼近。
- Q:相遇前快针转几圈? A:与环长和速度差有关。
02.3.1.2-012 如何判断交点在环上还是环外?
一句话结论
先求两链各自环入口;入口相同则环外某点合并后共用环;入口不同则检查一条链的环上是否含另一条入口;属带环相交的进阶判断。
概念解释
- 入口相同:公共环,环外可能相交。
- 入口不同:检查环上遍历。
- 标准面试题多为无环相交。
原理流程
- 各自判环求入口。
- 入口相同则沿环外对齐找交点。
- 不同则一链绕环查另一入口。
代码 / 图示
无环相交 → 换头/长度差
有环相交 → 先入口,再分环外/环内
常见误区
- 误区:无环相交方法直接套带环链;正解:带环链表尾为 null 不成立。
- 误区:环上引用比较会无限走;正解:绕环一圈即停。
追问
- Q:面试被问带环相交怎么答? A:先说明标准假设,再分入口相同/不同两步。
- Q:环上遍历一圈怎么停? A:记录起点,回到起点停止。
02.3.1.2-013 如何求环上距相遇点第 K 个节点?
一句话结论
从相遇点沿环走 K 步(模环长)即可;先求环长做取模;O(K) 时间 O(1) 空间。
概念解释
- 环形回绕:步数对环长取模。
- 方向:沿 next。
- 越界回起点。
原理流程
- 求环长 L。
- K %= L。
- 从起点走 K 步。
代码 / 示例
ListNode kthOnCycle(ListNode start, int k, int len) {
ListNode cur = start;
k %= len;
for (int i = 0; i < k; i++) cur = cur.next;
return cur;
}
常见误区
- 误区:K ≥ 环长未取模;正解:环形必须模周长。
- 误区:从 head 走 K 步;正解:在环上应从环内起点走。
追问
- Q:K 为负数? A:按题目口径反向或转正向步长。
- Q:环上随机节点? A:先定位入口再绕环。
02.3.1.2-014 判环题有哪些边界要注意?
一句话结论
空链表、单节点无环、自环(next 指自己)、两节点成环、环长与链长关系;循环条件必须同时保护 fast 与 fast.next。
概念解释
- 空与最短:fast 判空。
- 自环:单节点成环。
- 小环:两步速度下的相遇路径。
原理流程
- 入口判空。
- 构造自环与两节点环。
- 检查终止条件不越界。
代码 / 图示
null / [x] 无环
自环:x.next = x
两节点互指
常见误区
- 误区:访问 fast.next.next 不判 fast.next;正解:链式判空
fast != null && fast.next != null。 - 误区:自环检测不到;正解:两步后回到同点相遇。
追问
- Q:单节点 next=null? A:无环,fast 到 null 退出。
- Q:环入口等于头节点? A:二次同速在 head 相遇。
02.3.1.2-015 相交链表尾部共享有什么性质?
一句话结论
一旦相交,交点之后所有节点完全相同,尾部长度一致;因此从交点到尾的距离两条链相等,长度差只存在于交点之前。
概念解释
- 共享段:交点及以后同一批节点。
- 尾部对齐:独有段长度不同。
- 性质支撑长度差与换头法。
原理流程
- 交点之后引用相同。
- 尾部长度一致。
- 长度差落在独有段。
代码 / 图示
a: A1 → A2 → C1 → C2
b: B1 → C1 → C2
共享段 C1 → C2
常见误区
- 误区:相交后两条链可以有不同尾部;正解:共享尾部,不可分叉。
- 误区:值相同但节点不同也算相交;正解:引用必须相同。
追问
- Q:交点之后能分叉吗? A:单链表一个 next,不能分叉共享后再分开。
- Q:修改共享段影响谁? A:两条链都受影响。
02.3.1.2-016 快慢指针在其他链表题中的应用有哪些?
一句话结论
除判环找入口外,快慢指针还用于找中点、删除倒数第 N 个、判断回文后半段;核心都是利用速度差产生固定间距或半程位置。
概念解释
- 半程:找中点。
- 定距:倒数 N。
- 分段:回文前后半。
原理流程
- 明确要相对位置(中点/间距/分段)。
- 设定两针速度与初始间距。
- 终止时读取位置。
代码 / 图示
中点:同起点两步/一步
倒数 N:fast 先走 N
回文:中点切后半反转
常见误区
- 误区:所有双指针题都是判环;正解:按目标设定间距与速度。
- 误区:快慢指针必须相遇;正解:线性链以 fast 到尾终止。
追问
- Q:找中点偶数长度口径? A:条件不同可偏左或偏右。
- Q:定距指针怎么初始化? A:fast 先走完间距再同速。
02.3.1.2-017 二次同速找入口为什么不会走过?
一句话结论
由路程关系,head 到入口距离等于相遇点到入口的环内距离(差若干整圈);两针同速前进,步数相同,必然在入口相遇,不会越过。
概念解释
- 距离等式:a = c + 整圈。
- 同速:步长相同。
- 整圈不影响落点。
原理流程
- 从路程方程得入口距离关系。
- 两针同速出发。
- 到达入口时步数一致。
代码 / 图示
head →入口:a 步
相遇点 →入口:c + 整圈
同速走 a 步同时到达
常见误区
- 误区:二次指针速度不同;正解:必须同速一步。
- 误区:相遇点继续绕圈找入口;正解:回 head 同速更直接。
追问
- Q:如果有多个环? A:单链表结构上只会有一个环。
- Q:入口节点能直接从相遇点算出吗? A:需沿环走或二次同速定位。
02.3.1.2-018 如何判断两条无环链表是否相交(不要求交点)?
一句话结论
比较两链尾节点引用:相同则相交,不同则不相交;O(m+n) 时间 O(1) 空间;找交点再用换头或长度差法。
概念解释
- 共享尾部则尾节点相同。
- 尾节点不同必然不相交。
- 先判存在性再定位。
原理流程
- 分别走到尾部。
- 比较尾引用。
- 相同再找交点。
代码 / 示例
ListNode tailA = a, tailB = b;
while (tailA.next != null) tailA = tailA.next;
while (tailB.next != null) tailB = tailB.next;
boolean intersect = tailA == tailB;
常见误区
- 误区:比较尾节点值;正解:引用比较。
- 误区:尾相同但交点找不到;正解:再跑一次定位交点。
追问
- Q:空链表尾节点? A:null,按口径比较。
- Q:相交一定共享尾节点? A:是,单链表共享段延伸到尾部。
02.3.1.2-019 链表判环/相交的边界用例有哪些?
一句话结论
空、单节点、自环、两节点环、无环不相交、无环相交于头/中段/尾、长度差悬殊;覆盖引用相等与空指针终止。
概念解释
- 环边界:自环、小环。
- 相交边界:交点位置与长度差。
- 空指针:各阶段判空。
原理流程
- 构造空与最短链。
- 构造各类环与相交位置。
- 走查指针终止。
代码 / 图示
null / 单节点
自环 / 互指两节点
不相交 / 交于头 / 交于尾
长链 + 短链
常见误区
- 误区:相交题默认两链等长;正解:长度差由算法消除。
- 误区:环题未判空进入 fast.next;正解:链式判空。
追问
- Q:交点是头节点? A:一链整体并入另一链头,换头法仍成立。
- Q:环长等于链长? A:入口即头节点。
02.3.1.2-020 判环与相交的复杂度怎么汇报?
一句话结论
快慢判环 O(n) 时间 O(1) 空间;找入口再加 O(n);相交换头法 O(m+n) 时间 O(1) 空间;哈希对照 O(n) 空间;引用比较 O(1)。
概念解释
- 线性扫描:每个节点访问常数次。
- 辅助空间:指针或集合。
- 环内遍历绕圈有界。
原理流程
- 统计扫描轮次。
- 标注辅助结构。
- 区分双指针与哈希法。
代码 / 图示
判环:O(n) / O(1)
找入口:O(n) / O(1)
相交:O(m+n) / O(1)
哈希对照:O(n) / O(n)
常见误区
- 误区:找入口要绕多圈所以超线性;正解:环长有限,总访问 O(n)。
- 误区:相交换头法最坏 O(m+n) 还重复遍历;正解:每链节点最多访问两次。
追问
- Q:带环链表求长度? A:需先定位入口与环长,链外长度 + 环长。
- Q:哪些题必须 O(1) 空间? A:面试明确要求常数空间时用双指针,哈希法作备选。