链表检测环并找入口（Linked List Cycle II）
力扣 141（判断有环）+ 142（找入口），用一套思路全解决。
解法：Floyd 判圈算法（龟兔赛跑）
用快慢两个指针，slow 每次走 1 步，fast 每次走 2 步：
- 无环：
fast先到 null - 有环：
fast和slow一定在环内相遇
cpp
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
// 第一阶段：判断有无环，找相遇点
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// 第二阶段：找环入口
ListNode* finder = head;
while (finder != slow) {
finder = finder->next;
slow = slow->next;
}
return finder; // 相遇点即为环入口
}
}
return nullptr; // 无环
}
为什么第二阶段能找到入口？数学推导
设：
head 到环入口的距离 = a 环入口到相遇点的距离 = b 相遇点到环入口的距离 = c（即环长 - b）
head ──a──> [入口] ──b──> [相遇点]
└──────c──────┘（绕回入口）
第一阶段，相遇时：
slow走了：a + bfast走了：a + b + n*(b+c)（在环里多绕了 n 圈）- 因为 fast 速度是 slow 的 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 最简情况：a = c
结论：从 head 出发走 a 步，从相遇点出发走 c 步，两者同时到达环入口。
所以第二阶段把一个指针重置回 head，两个指针同速前进，相遇点就是环入口。
可视化走一遍
链表: 3 → 1 → 2 → 0 → (-4)
↑___________↑ (−4 的 next 指向 1，入口是节点 1)
a=1（head→入口），b=3（入口→相遇点），c=1（相遇点→入口）
验证：a = c = 1 ✓
第一阶段相遇在 (-4)：
slow: 3→1→2→0→(-4) 走了 4 步
fast: 3→2→(-4)→2→(-4) 走了 4×2=8 步（在环里绕了一圈）
第二阶段：
finder 从 head(3) 出发，slow 从相遇点(-4) 出发
同走 1 步：finder=1，slow=1 ← 相遇，返回节点 1 ✓
复杂度
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(n) | 两个阶段各最多走一圈 |
| 空间 | O(1) | 只用两个指针，无额外空间 |
哈希表也能做（记录访问过的节点），但空间是 O(n)，面试中直接说 Floyd 算法即可。
面试时的表达顺序
先说快慢指针一定会在环内相遇（因为 fast 比 slow 每轮多走 1 步，相对速度 1，环内必追上）→ 再给出数学推导 a = c（或 a = (n-1)L + c）→ 然后写代码。把推导过程说出来，是这道题拿满分的关键。