LeetCode 面试题 02.08. 环路检测
题目描述
题意分析
若沿
next能再次回到某个已经访问过的节点，链表就存在环，需要返回从头节点出发第一次进入环的那个节点；不存在环则返回空。返回的是原节点引用，节点值相同不代表它们是同一个节点。题目中的
pos只用来描述尾部接回的位置，不会作为参数传入。要满足常数额外空间的要求，可以先用快慢指针确认有环，再由相遇位置推导环入口。
解法：快慢指针
核心思路
[!blue]
先判断是否有环。令
slow、fast都从头节点出发，每轮分别走一步、两步，再比较节点引用。如果没有环，快指针最终会到达空指针，或停在没有后继的末节点；循环结束后返回空即可。如果有环，慢指针进入环时，快指针也已经在环内。此后快指针每轮比慢指针多走一步，两者在环上的相对位置每轮改变一格，因此最多再经过一圈的轮数就会相遇。第一次相遇只能说明存在环，相遇点未必是入口。
再定位入口。设从头到入口的距离为
a，入口沿环到相遇点的距离为b，环长为c。慢指针相遇时一共走了t步，它可能已经多绕了k圈，所以有 $t=a+b+kc$；快指针走了2t步，二者相遇在同一个节点，路程之差t必须是环长的整数倍。消去整圈可知，a + b也是c的整数倍。把一个新指针
p放回头节点，让它和相遇点上的slow都每轮走一步。走a步后，p刚好到入口；slow从环上偏移b的位置再走a步，总偏移a + b恰为整圈，也回到入口。这还是第二阶段的第一次相遇：在走满
a步之前，p位于环外，slow始终位于环内，不可能指向同一节点。如果入口本来就是头节点，a = 0，两个指针在第二阶段开始时就已相同，无需再移动。快指针每轮要走两步，必须先判断
fast非空，再判断fast.next非空。第一阶段要在移动后比较，不能把两个指针初始都位于头节点误当作有环。空链表、无环单节点和自环也都由这两个阶段自然处理。
解题步骤
- 初始化
slow = head、fast = head。- 当
fast及其后继均非空时，慢指针走一步、快指针走两步，再判断两者是否指向同一节点。- 若相遇，令
p = head，让p与slow同步每次走一步，直到相同，返回该节点。- 若第一阶段因快指针无法继续前进而退出，返回空。
代码实现
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode 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;
}
}
func detectCycle(head *ListNode) *ListNode {
// 令一个指针回到头节点，两个指针同步前进，再次相遇点即为入环点。
slow, fast := head, head
// 快指针一次走两步，必须先保证两次访问均有入口。
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
// 相遇后以相同速度前进，头部距离与环内剩余距离在入口对齐。
p := head
for p != slow {
p = p.Next
slow = slow.Next
}
return p
}
}
return nil
}
复杂度分析
- 时间复杂度：$O(n)$，
n为从头可达的不同节点数。有环时第一阶段至多经过入环距离加一圈的轮数，第二阶段再走入环距离；无环时快指针直接到达末尾。- 空间复杂度：$O(1)$，只使用固定数量的节点指针，不记录访问集合，也不修改链表。
关键点总结
[!green]
- 第一次相遇点通常不是入口。
- 入口证明依赖一倍与两倍速度对应的整圈关系。
易错点总结
[!yellow]
- 直接返回第一次相遇点，会返回环内其他节点。
- 检测阶段漏掉 fast.next 的空判断，会访问空指针。
- 比较节点值是否相等，会把不同的同值节点误当成相遇；应比较节点引用或指针。
- 改成三倍速度后仍照搬入口重置步骤，原来的距离关系不再保证成立。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 141. 环形链表 | 简单 | 先用快慢指针判断有环，本题还要根据相遇位置推导并寻找入环点。 |
| 287. 寻找重复数 | 中等 | 把数组下标跳转视为函数图，可复用找环入口的方法确定重复值。 |