快慢指针相遇的那一点，为什么不是环的入口
快慢指针判环只用两个指针和 O(1) 空间：慢的走一步、快的走两步，有环必相遇，无环则快指针先撞到 null。真正容易被问倒的是后半段——相遇点通常不是环的入口，必须把一个指针放回头结点、两者同速再走，才会在入口会合。这个结论来自一条同余等式，而网上常见的“相遇点到入口的距离等于头到入口的距离”在尾链长于环长时并不严谨。另一个高频坑是步长：快指针走三步并不总能追上，环长为偶数时可能永远错身而过。读完你能自己推出入口位置、写对边界判断，并知道什么时候该改用哈希或 Brent 算法。
是什么
快慢指针判环（Floyd 判圈，也叫龟兔赛跑算法）是这样一个约定：两个指针从链表头同时出发，慢的每次走一步，快的每次走两步。如果链表没有环，快指针迟早走到 null，循环结束；如果有环，快指针会先进入环里绕圈，最终从后面追上慢指针，两者指向同一个节点。
它解决的是“这个结构会不会绕回自己”的问题，而且不用额外开一张访问记录表：时间 O(n)，空间 O(1)。常见场景有三类：判断单链表是否有环并定位入口；在“每个下标只指向一个后继”的函数图上找重复值，比如 n+1 个数取值落在 1 到 n 的找重复题；检测伪随机序列、哈希迭代或大整数分解里的周期。它也被借用来排查对象引用成环、状态机死循环这类问题——只要你能把“下一个状态”写成 next。
值得先记住的直觉是：有环的时候没有终点，快指针不是“先到”，而是“多跑”。它会套圈，而套圈这件事只要相对速度合适，就一定会发生。
核心原理
先约定符号：从头结点走到环入口要经过 a 条边，环上一共有 C 个节点。慢指针走完 a 步、刚踏进环时，快指针已经走了 2a 步，也就是在环内多走了 a 步，停在入口往前 a mod C 的位置。
此刻两者在环上的“前向间距”（从快指针沿指针方向走到慢指针要几步）是 (C - a mod C) mod C。之后每走一轮，慢的进 1、快的进 2，这个间距就减少 1；减到 0 的那一轮，两者落在同一个节点上。由于间距每轮严格减 1、而且始终在 0 到 C-1 之间变化，它必然会经过 0，快指针不会“从旁边跳过去”。
用同余写更干脆。设相遇发生在慢指针进环之后又走了 t 步，那么慢指针总步数是 a+t，快指针是 2(a+t)。两者落在同一位置，当且仅当它们的步数对 C 同余，也就是 a + t ≡ 2(a + t) (mod C)，移项得到 t ≡ -a (mod C)。
取最小的可行 t（慢指针进环后最多再走一圈就会被追上），就得到相遇点。把式子移项，从相遇点沿指针方向再走 a 步，位置是 t + a ≡ 0 (mod C)，正好是入口。而头指针走 a 步也正好是入口——两条路径的终点重合，这就是“把快指针放回头结点、两个指针都改成每次一步，再相遇处即入口”的全部依据。注意这里走的是 a 步，不是“a 条边的直线距离”：如果尾链比一圈还长，慢指针要从相遇点绕几个整圈才回到入口，所以“相遇点到入口的距离等于头到入口的距离”这句话只在尾链不超过一圈时成立，严谨的说法是“再走 a 步必到”。
拿一组数字走一遍更直观：尾链 3 条边、环长 5。慢指针刚进环时快指针在环内第 4 个位置，间距 2；两轮后两者在环内第 3 个位置相遇（慢指针在环里只走了 2 步）。这时从头和从相遇点各走 3 步——头指针正好踏进入口，慢指针从第 3 个位置经过第 4、第 5 个再回到入口——两者在入口会合，且此前不可能提前碰上，因为头指针那 3 步全在环外的尾链上。
代码只有十来行：
def cycle_entry(head):
slow = fast = head
while fast and fast.next: # 先判空，再取 next.next
slow = slow.next
fast = fast.next.next
if slow is fast: # 用身份比较，不用 ==
p = head
while p is not slow:
p = p.next
slow = slow.next
return p # 入口；也可能是 head
return None # 无环为什么步长偏偏是 2？因为相对速度是 1，间距每轮减少 1，与环长 C 一定互质。换成 3 就不保证了：相对速度变成 2，若 C 是偶数，间距的奇偶性就被锁死。举个具体的例子，环长 4，慢的在 0、快的在 1，每轮慢的加 1、快的加 3，位置依次是 (0,1) 到 (1,0) 到 (2,3) 到 (3,2) 再回到 (0,1)，永远错身而过。所以“只要快比慢快就行”是错的，条件其实是步长减一与 C 互质；而 C 事先未知，只有步长 2（相对速度 1）对所有 C 都成立。
常见考点与误区
- 误区一：相遇点就是环的入口。 这是最常见的错答。相遇点只在 a 是 C 的整数倍这类巧合下才恰好是入口；一般情况下它只是快指针追上来的地方，还必须借助“从头再走一遍”才能定位入口。
- 误区二：找入口时让快指针保持两倍速。 等式依赖两个指针走相同的步数 a，必须都改成每次一步，且其中一个从相遇点、另一个从头出发。继续用两倍速会破坏这个对称性，结果随环长漂移。
- 误区三：快指针步长随便取，3、4、5 都行。 见上面的反例：相对速度与环长不互质时会永远错过。这是面试里区分“背过结论”和“推过证明”的一题。
- 考点四：慢指针会不会在环里转很多圈才被追上？ 不会。它的总步数是 a 加 t，而 t 不超过一圈，所以整体仍是 O(n)；只有入口恰好是头结点时是例外，两个指针出发就重合，代码往往要等它们跑满一圈才在入口再次相等。转很多圈的是快指针。
- 考点五：循环条件为什么是
fast and fast.next？ 因为循环体里要取fast.next.next。只判fast的话，快指针落到最后一个节点时fast.next已经是 None，再取一层就直接抛异常。 - 误区六：哈希表判环更“稳”，所以 Floyd 没必要学。 哈希集合写法更短，还能顺手返回沿途节点，代价是 O(n) 额外空间、对缓存不友好。Floyd 的价值在 O(1) 空间与“流式、不可回访”的场景，比如只能顺序求值的函数迭代，不是在所有场景都更快。
实践建议
- 把边界用例固定成一张表：空链表、单节点自环、两节点互指、入口在头（a 等于 0）、入口在尾、环长为奇数与偶数。a 等于 0 时最容易误判，因为两个指针出发时就在同一点，代码的首次相等判断必须放在移动之后。
- 比较节点用
is，不要用==。一旦节点类重写了相等判断（按值比较），两个不同节点可能被判成同一个，判环直接失效。 - 需要“入口、环长、首个重复节点”这类附加信息时，别硬套 Floyd：先用哈希表拿到答案，再评估是否值得为省内存重写。纯判环且内存敏感时才优先 Floyd。
- 函数求值很贵时（大整数分解、哈希链），可以换 Brent 算法：它按 2 的幂次设检查点，比较次数通常只有 Floyd 的三分之二左右，渐近复杂度相同。
- 迁移练习：把“下标 i 指向 nums[i]”看成 next，就能用同一套代码解“找重复数”；先确认值域落在下标范围内，否则图里会出现越界边，算法前提不成立。
一句话总结：相遇点只是快指针追上来的坐标，再走 a 步才回到入口；步长 2 可靠，是因为相对速度 1 与任何环长都互质。