LeetCode 142. 环形链表 II
题目描述
题意分析
如果沿着
next不断前进会再次到达同一个节点，链表就有环。本题需要返回第一次进入环的那个节点本身；没有环则返回空，不能只返回是否有环或节点值。节点值可以重复，因此相遇必须判断是不是同一个节点。题面中的
pos只是描述尾节点接回了哪里，不会作为参数传入；算法只能从head出发，且不能修改节点或断开链表。进阶要求只使用常数额外空间，空链表、环入口就是头节点、单节点自环都需要覆盖。
解法：Floyd 快慢指针
核心思路
[!blue]
先确定有环，再定位入口。让
slow和fast同时从头节点出发，每轮分别前进一步、两步。无环时，快指针最终会到达空节点；有环时，两者最终都会进入环，此后快指针每轮相对慢指针多走一步，它们在环上的距离会按环长循环，最多再经过一圈就会相遇。第一次相遇说明有环，但相遇点通常不是入口。为什么相遇后能找入口？设头节点到入口的距离为
a，入口沿next到相遇点的距离为b，环长为L。相遇时慢指针共走了s步，快指针走了2s步；它们位于同一节点，所以路程差s必须是环长的整数倍。慢指针的路程也可以写成s = a + b + kL，其中k表示可能多走的整圈数，因此a + b同样是L的整数倍。这意味着：从相遇点继续走
a步，环内累计偏移为b + a，恰好回到入口。于是把一个指针移回头节点，另一个留在相遇点，两者都改为每轮走一步。走完a步时，一个刚好从链表前缀到达入口，另一个也刚好沿环到达入口。这还是第二阶段的第一次相遇：来自头节点的指针在到达入口之前一直位于环外，另一个指针始终在环内，两者不可能提前相等。若入口就是头节点，
a = 0，重置后已经相等，直接返回即可，不应再强制移动一次。
解题步骤
- 将
slow、fast都指向head。每轮先确认fast和fast.next均非空，再分别前进一步、两步。- 移动后比较两个节点引用。若始终没有相遇、循环因空指针边界结束，返回空，表示无环。
- 发现相遇后，将
fast重置为head，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)$，
n为链表中不同节点的总数。有环时，慢指针走过环外前缀后至多再走一圈即可相遇，定位入口再走一次前缀；无环时直接遍历到末尾。- 空间复杂度：$O(1)$，只使用两个节点指针和固定数量的局部变量。
关键点总结
[!green]
- 相遇判断比较节点身份，节点值相同不能证明有环。
- 第一次相遇靠速度差追及，第二次相遇靠
a + b是环长整数倍来对齐入口。- 第二阶段必须同速，而且先判断是否相等，再决定是否继续移动。
- 全程只移动局部指针，不修改任何节点的
next。
易错点总结
[!yellow]
- 两个指针初始都在头节点，第一阶段若在移动前比较，会把这种初始相等误判为有环。
- 只检查
fast而不检查fast.next，执行两步跳转时可能访问空节点。- 直接返回第一次相遇点，会把环内任意相遇位置误当成入口。
- 第二阶段仍让一个指针走两步，破坏两者都走
a步到入口的保证。- 用节点值判断重复，或者为了标记访问修改节点，都不符合题目要求。
如果不要求常数空间，也可以用集合记录访问过的节点身份：第一次遇到已记录的节点时，它就是入口，因为环外节点只会经过一次，而沿环走完一圈首先回到入口。该方法时间和额外空间均为 $O(n)$。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 141. 环形链表 | 简单 | 先用快慢指针判断有环，本题还要根据相遇位置推导并寻找入环点。 |
| 287. 寻找重复数 | 中等 | 把数组下标跳转视为函数图，可复用找环入口的方法确定重复值。 |
| 202. 快乐数 | 简单 | 用快慢指针确定环或中间位置；本题在相遇后推导环入口，该题将数字变换视为隐式后继关系。 |
| 补充题 188. 链表断环 | 中等 | 沿用快慢指针定位入环点；补充题再寻找入口前驱并断开环。 |