Floyd 快慢指针：兔子和乌龟为什么一定相遇？
一句话结论（30s）
快慢指针（2 步 vs 1 步）一定能在环内相遇且不会错过，是因为快指针每步只比慢指针多走 1 步、相对距离每步缩小 1，最多 d 步必然追到；相遇后让两个指针等速从表头和相遇点同时出发，再次相遇处就是环入口（因为 a = (n-1)L + c）。
核心原理（2min）
- 检测环：快 2 慢 1，环内追赶相对速度恒为 1，距离每步缩小 1，不会跳过（走 3 步则可能一步跨过去，需要运气）。为什么会想到”相对速度”这个角度？ 因为两人在环里转圈，谁先到不好判断，但把”快-慢”转成”相对速度差”后，问题就从”两个人在绕圈”退化成”一个点以恒定速度 1 逼近另一个点”，距离单调递减、必然归零。
- 找入口：数学推导 a + b = nL → a = (n-1)L + c，故从表头走 a 步 = 从相遇点走 (n-1)L + c 步，二者在环入口重逢。
- 找环长：相遇后一指针不动、另一指针再走一圈回到相遇点的步数即环长 L。
底层深入（5-10min）
第一步：检测有环（相遇）
快指针每次走 2 步，慢指针每次走 1 步。如果存在环，两个指针一定会在环内相遇。
为什么不是错过？
慢指针进入环时，快指针在环中某个位置。快指针每次比慢指针多走 1 步。在环中，快指针以每步 1 的速度”追赶”慢指针。 每步缩小距离 1，当前距离 d，最多 d 步后相遇。不会错过。
如果快指针走 3 步 → 每步缩小距离 2 → 可能跳过距离为 1 时（一步跨过去）→ 可能错过→ 需要运气。走 2 步是最保险的。为什么不选更大的步长加速？ 步长一大，相对速度从 1 变成 2、3，缩距不再”逐一递减”，当剩余距离不被相对速度整除时就会直接跨过、甚至永远错位——步长 2 恰好让相对速度恒为 1，是”最快”与”最稳”的平衡点。
💭 思考：看到什么信号该想到快慢指针？——链表的题一旦同时出现「可能有环」+「要求 O(1) 空间」，哈希表（要 O(n) 空间）就出局了；此时只能用有限几个指针”原地”探测，而”环”意味着转圈、意味着追击，于是”两个不同速度的指针”自然浮现：把”找环”翻译成”一个人追另一个人，快者每步只逼近 1，终会追上”。
第二步：找到环的入口
相遇后，将一个指针放回链表头，两个指针同速（每步 1）前进。再次相遇的位置就是环的入口。
为什么？数学推导：
链表头 → 环入口 = a 步
环入口 → 相遇点 = b 步
相遇点 → 环入口 = c 步（环的长度 L = b + c）
慢指针走了: a + b
快指针走了: a + b + nL（多绕了环 n 圈）= 2(a + b)
→ a + b = nL
→ a = (n-1)L + c
→ 从链表头走 a 步 = 从相遇点走 (n-1)L + c 步 = 到达环入口
→ 从链表头和相遇点同时等速走 → 在环入口相遇💭 思考：怎么一步步推出
a = (n-1)L + c？——别背公式，按”快慢指针走过的路程”列方程：设慢指针走了a + b，快指针速度是它两倍、且多绕了 n 圈，所以2(a + b) = a + b + nL，约掉即a + b = nL。关键一步是意识到a = nL - b，而nL - b = (n-1)L + (L - b) = (n-1)L + c——也就是”从相遇点再走 c 步绕 n-1 圈”正好回到入口。于是”从表头走 a 步”和”从相遇点走等价步数”必然在入口汇合。
完整代码
ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 有环
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr; // 环入口
}
}
return null; // 无环
}扩展：找环的长度
相遇后，一个指针不动，另一个继续走并计数，再次回到相遇点时的步数 = 环的长度。
💭 思考：求环长为什么这么直白？——因为”环的长度”的定义就是”从环上一点出发、绕一圈回到原点的步数”；相遇点一定在环上，所以拿相遇点当起点数一圈就是 L，不用任何额外推导。想通这一点，“环检测 / 环入口 / 环长度”三个问题就被同一套”相遇点”串起来了。
总结
Floyd 算法的两个数学结论：
- 快慢指针（2 步 vs 1 步）在环中必然相遇，且不会跳过
- 相遇点到环入口的距离 + 环长度倍数 = 链表头到环入口的距离，故两指针等速出发在环入口相遇
章末提问
-
为什么快慢指针相遇后，一个回头、一个不动，等速走就一定在环入口相遇？ 结论：因为
a = (n-1)L + c，即”表头到入口的距离”等于”相遇点绕 n-1 圈再走 c 步”的距离；所以从表头走 a 步和从相遇点走等价步数会同时落到入口。 -
快指针走 3 步一定检测不到环吗？ 结论：不一定，只是”可能”错过，因为相对速度变成 2，剩余距离为 1 时会被一步跨过；但只要没有恰好错位，还是能相遇，只是不再有”必然相遇”的保证。
-
如何用这个算法求环的长度？ 结论：相遇后一个指针原地不动、另一个继续走并计数，再次回到相遇点所走的步数就是环长；因为从环上某点出发绕一圈回到原点的步数恰好等于 L。