题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
不允许修改链表。
题目分析
这道题是 环形链表 的进阶版。
上一题“环形链表”只需要判断链表中是否有环，因此只要快慢指针能够相遇，就可以直接返回 true。
而这道题更进一步，不仅要判断链表中有没有环，还要找到 环开始的位置，也就是入环点。
-
遍历链表，把访问过的节点放进哈希表；
-
如果某个节点第二次出现，那么这个节点就是入环点。
这个思路当然可以做，但是需要额外空间。
这题更经典的做法依然是 快慢指针，并且空间复杂度可以做到 O(1)。
核心思路
整道题可以分成两个步骤：
第一步：判断链表中是否有环
定义两个指针：
-
slow每次走一步 -
fast每次走两步
如果链表中有环，那么这两个指针迟早会在环中相遇。
如果链表没有环，那么 fast 会先走到 null，这时直接返回 null 即可。
第二步：找到入环点
当快慢指针第一次相遇之后：
-
让
fast回到链表头节点head -
然后让
slow和fast每次都走一步 -
当它们再次相遇时，相遇的位置就是 入环点
这一步是这道题最关键的地方。
为什么再次相遇的位置就是入环点？
这是这道题最经典的数学结论。
假设：
-
从头节点到入环点的距离是
a -
入环点到第一次相遇点的距离是
b -
环的剩余长度是
c
那么环的总长度就是：
b + c
当快慢指针第一次相遇时：
-
慢指针走过的路程：
a + b -
快指针走过的路程：
a + b + n(b + c)-
这里的
n表示快指针比慢指针多转的环数
-
因为快指针速度是慢指针的 2 倍，所以：
2(a + b) = a + b + n(b + c)
整理一下：
a + b = n(b + c)
再变形：
a = n(b + c) - b
写成更容易理解的形式：
a = (n - 1)(b + c) + c
这说明什么？
说明从 头节点走到入环点的距离 a，恰好等于从 第一次相遇点继续往前走 c 步，再绕若干圈 到入环点的距离。
所以：
-
一个指针从
head出发 -
一个指针从第一次相遇点出发
-
两个指针每次都走一步
那么它们一定会在 入环点 相遇。
代码实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
代码讲解
1. 初始化快慢指针
ListNode fast = head, slow = head;
一开始两个指针都指向头节点。
2. 先判断链表中是否有环
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
这里使用死循环配合返回和 break：
-
如果
fast == null或者fast.next == null，说明链表无环，直接返回null -
否则让快慢指针继续前进
-
如果两个指针相遇，说明链表有环，退出循环
这一段和上一题“环形链表”的判断逻辑基本一致。
3. 让一个指针回到头节点
fast = head;
相遇之后，把 fast 放回头节点。
此时：
-
slow留在第一次相遇点 -
fast从头节点重新出发
4. 两个指针同步前进
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
这时候两个指针都改为一次走一步。
根据上面的推导，它们会在入环点再次相遇。
5. 返回入环点
return fast;
因为相遇位置就是入环点，所以直接返回任意一个指针即可。
示例分析
假设链表如下：
3 -> 2 -> 0 -> -4
^ |
|_________|
其中值为 2 的节点是入环点。
第一步：快慢指针第一次相遇
-
slow每次走一步 -
fast每次走两步
它们最终会在环中的某个位置相遇，但这个位置不一定是入环点。
比如可能会在值为 -4 的节点相遇。
第二步：寻找入环点
-
把
fast放回头节点3 -
slow留在第一次相遇点-4 -
然后两个指针每次都走一步
最终它们会在值为 2 的节点再次相遇。
所以返回该节点即可。
为什么不能直接返回第一次相遇点？
因为 第一次相遇点只是在环内，不一定是入环点。
快慢指针第一次相遇时，只能说明链表有环，但还不能直接说明当前节点就是环的起点。
因此必须进行第二轮同步移动，才能真正找到入环点。
复杂度分析
时间复杂度
O(n)
虽然看起来有两个阶段：
-
快慢指针判断是否有环
-
再次寻找入环点
但两个阶段加起来，整体遍历次数仍然是线性级别，所以时间复杂度为 O(n)。
空间复杂度
O(1)
整个过程中只用了几个指针变量，没有使用额外数据结构。
和哈希表解法对比
哈希表解法
思路是把遍历过的节点存入集合中：
-
如果某个节点第一次出现，就加入集合
-
如果某个节点第二次出现，说明它就是入环点
这种做法的优点是思路直接，容易理解。
但缺点也很明显：
-
需要额外的
O(n)空间
快慢指针解法
优点：
-
不需要额外空间
-
是这道题最经典、最优雅的做法
缺点：
-
数学推导稍微抽象一些
-
第一次接触时不太容易一下想明白
面试中如果能写出快慢指针解法，并且解释清楚为什么第二次相遇是入环点，一般会非常加分。
总结
这道题的关键点有两个：
-
先用快慢指针判断链表是否有环
-
相遇后让一个指针回到头节点，两个指针同步前进，再次相遇的位置就是入环点
这类题目非常经典，建议和上一题“环形链表”放在一起记忆：
-
141 题：判断有没有环
-
142 题：找到环的入口
前者重点在于“快慢指针能否相遇”，后者重点在于“相遇后如何找到入环点”。
