LeetCode 142. 环形链表 II
目录
题目描述
题意分析
给定链表的头节点，如果链表中存在环，返回「链表开始入环的第一个节点」；如果不存在环，返回空。注意本题要的是入环节点本身，而不是判断有没有环——只判有无环是 141 题，本题在此之上还要精确定位。
节点的身份只能靠引用区分，节点值完全可能重复，任何基于值的判断都不可靠。题目进阶要求用 $O(1)$ 空间解决，这暗示除了「记住走过哪些节点」之外，还存在只依赖常数额外空间的定位方式。
边界上要注意：空链表和无环链表都应返回空；环可能从头节点就开始，整条链表都在环上；也可能是单个节点指向自己的自环。
解法：Floyd 快慢指针
核心思路
先用快慢指针判断是否有环。相遇后，将一个指针移回头节点，两个指针改为每次走一步；它们再次相遇的位置就是入环点。
设头节点到入口距离为
a，入口到首次相遇点距离为b，环长为L。首次相遇时快指针比慢指针多走整数圈，因此a + b = kL，即a = (k - 1)L + (L - b)。所以从头节点和相遇点同时前进，会在入口相遇。
解题步骤
slow每次走一步，fast每次走两步；若快指针到达空节点，则无环。- 两指针首次相遇后，将
fast移回head。fast、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) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
func detectCycle(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
}
return nil
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
关键点总结
- 第一次相遇只能确认存在环，不能直接作为入口。
- 定位入口时两个指针必须同速移动。
- 判环循环要同时检查
fast和fast.next。
易错点总结
- 在移动前比较初始指针，两者必然相等，会把无环链表误判为有环。
- 只检查
fast != null，访问fast.next.next时可能空指针。- 第二阶段仍让快指针走两步，无法保证在入口相遇。
- 无环时应返回空，不能返回循环退出时的任一指针。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 141. 环形链表 | 简单 | 只判断环是否存在，无需定位入口 |
| 202. 快乐数 | 简单 | 把数字迭代序列当隐式链表判环 |
| 287. 寻找重复数 | 中等 | 数组下标映射成隐式链表后找入口 |
| 457. 环形数组是否存在循环 | 中等 | 环形数组上带同方向约束的循环判定 |
| LCR 022. 环形链表 II | 中等 | 本题在 LCR 题库中的同题变体 |
| 面试题 02.08. 环路检测 | 中等 | 本题在面试金典中的同题变体 |