一、题目概述
给定一个链表的头节点 head，如果链表中存在环，返回环的入口节点。如果链表无环，返回 null。
这道题是 LeetCode-141（判断链表是否有环）的进阶版。141 只需要判断"有没有环"，而这道题要求你找到环开始的那个节点。
示例 1
3 -> 2 -> 0 -> -4^ ||___________|
pos = 1
输出：
返回索引为 1 的节点（值为 2）
示例 2
1 -> 2
^ |
|____|
pos = 0
输出：
返回索引为 0 的节点（值为 1）
示例 3
1
pos = -1（没有环）
输出：
None
二、核心思路
第一步和 141 一样：快慢指针判环
先用快慢指针判断链表是否有环。慢指针每次走 1 步，快指针每次走 2 步。如果有环，它们一定会在环内某个节点相遇。
这一步在 141 题中已经讲过，不再展开。
第二步才是关键：找环的入口
快慢指针相遇之后，我们知道链表有环了，但相遇点不一定是环的入口。
Floyd 判圈算法的第二阶段是这样做的：
- 把其中一个指针重置到
head（链表头部） - 另一个指针留在相遇点
- 然后两个指针都每次走 1 步
- 它们再次相遇的地方，就是环的入口
这看起来像魔法，但背后有严格的数学证明。
为什么 a = c：数学推导
我们给链表各段起个名字：
head ----a---- 入口 ----b---- 相遇点^ ||_______c________|
a：从head到环入口的距离b：从环入口到相遇点的距离c：从相遇点继续沿环走回到环入口的距离- 环的长度 =
b + c
当快慢指针相遇时：
- 慢指针走了
a + b步 - 快指针走了
a + b + n(b + c)步（快指针在环里多转了n圈，n >= 1）
因为快指针的速度是慢指针的 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
这个等式说明什么？
(n - 1)(b + c)是整数圈的距离，走完之后还是回到相遇点- 所以
a = c + 若干整圈
也就是说：从 head 走 a 步到达环入口，和从相遇点走 c 步（再加若干整圈）也到达环入口。
所以，如果两个指针分别从 head 和相遇点出发，每次都走 1 步，它们一定会在环的入口相遇。
最简单的情况下 n = 1（快指针只多转了一圈），此时 a = c，从 head 到入口的距离恰好等于从相遇点到入口的距离。
三、代码实现
class Solution:def detectCycle(self, head: ListNode) -> ListNode:slow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None
四、逐行拆解
1. 初始化快慢指针
slow = head
fast = head
和 141 题一样，两个指针都从链表头部出发。
2. 第一阶段：快慢指针找相遇点
while fast and fast.next:slow = slow.nextfast = fast.next.next
慢指针每次走 1 步，快指针每次走 2 步。循环条件保证快指针能安全地走两步。
如果链表无环，快指针会先走到 None，循环结束。
3. 判断相遇
if slow == fast:
如果快慢指针指向了同一个节点，说明链表有环，且这个节点就是环内的相遇点。
4. 第二阶段：找环入口
slow = head
while slow != fast:slow = slow.nextfast = fast.next
return slow
关键操作：
- 把
slow重置到head fast留在相遇点- 两个指针现在都每次只走 1 步
- 它们再次相遇的节点就是环的入口
根据前面的数学推导，从 head 到环入口的距离 a，等于从相遇点沿环走到入口的距离 c（可能加若干整圈），所以两个指针一定会在入口处碰面。
5. 无环则返回 None
return None
如果 while 循环因为 fast 或 fast.next 为 None 而结束，说明链表没有环，返回 None。
五、手动模拟
有环的情况
3 -> 2 -> 0 -> -4^ ||___________|
节点索引：3(0) -> 2(1) -> 0(2) -> -4(3) -> 2(1)（回到索引 1）
第一阶段：找相遇点
| 步骤 | slow | fast |
|---|---|---|
| 初始 | 3 | 3 |
| 第 1 步 | 2 | 0 |
| 第 2 步 | 0 | 2（-4 -> 2，绕回环内） |
| 第 3 步 | -4 | -4 |
第 3 步 slow == fast，在节点 -4 处相遇。
第二阶段：找入口
slow重置到head（节点 3）fast留在相遇点（节点 -4）
| 步骤 | slow | fast |
|---|---|---|
| 初始 | 3 | -4 |
| 第 1 步 | 2 | 2 |
第 1 步 slow == fast，在节点 2 处相遇。节点 2 正是环的入口，返回它。
验证一下：a = 1（从 head 到入口走 1 步），c = 1（从相遇点 -4 沿环走 1 步回到入口 2），确实 a = c。
无环的情况
1 -> 2 -> 3 -> None
| 步骤 | slow | fast |
|---|---|---|
| 初始 | 1 | 1 |
| 第 1 步 | 2 | 3 |
| 第 2 步 | 3 | None（fast.next 为 None，退出） |
循环正常结束，返回 None。
六、复杂度分析
时间复杂度：O(n)
- 第一阶段：快慢指针相遇最多需要 O(n) 步（慢指针最多走一圈多一点）
- 第二阶段：两个指针从 head 和相遇点出发，最多再走 O(n) 步就能在入口相遇
- 总体是线性时间
空间复杂度：O(1)
只用了两个指针变量，没有额外的数据结构。
如果用哈希表记录访问过的节点也能解这题，但空间复杂度会变成 O(n)。Floyd 算法的优势就在于只用常数空间。
七、总结
这道题的标准解法是：
class Solution:def detectCycle(self, head: ListNode) -> ListNode:slow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None
最值得记住的三个要点：
- 两个阶段：第一阶段用快慢指针找到环内的相遇点，第二阶段用两个同速指针找环入口
- 数学本质：
a = (n-1)(b+c) + c，从 head 走到入口的距离等于从相遇点走到入口的距离（加若干整圈），所以两个指针同速出发一定在入口相遇 - 重置 slow 到 head：相遇之后不是两个指针都回到 head，而是只把一个指针拉回 head，另一个留在相遇点，然后都走 1 步
这道题是 Floyd 判圈算法的完整版。141 题只用了算法的前半段（判环），142 题把后半段（找入口）也补上了。理解了 a = c 背后的数学关系，这个算法就不再是需要死记的套路，而是一个可以自己推导出来的结论。