Fast & Slow · Floyd

快慢指针：一步 vs 两步，找出环和中点

快慢指针主要用于链表问题。链表的局限在于每个节点只能看到自己的 next，无法像数组那样随机访问第 i 个元素。让 slow 每次走一步、fast 走两步，这个速度差就换来了对前方 / 后方结构的感知。同一套机制，下面演示四种用法：

判圈为什么一定能相遇？一旦两个指针都进了环，就把它们看成在一条环形跑道上：fast 每步比 slow 多走 1 个身位，它们的「距离」每步减 1，必然归零——也就是相遇。fast 不会「跳过」slow，因为每步只逼近一格。无环则 fast 先到达 null，即可判定没有环。时间 $O(n)$ 、空间 $O(1)$ （对比「用 HashSet 记访问过的节点」要 $O(n)$ 空间）。

找环入口的数学（用法「已知有环，找环的入口」）：设头到入口距离 a、入口到相遇点 b、环长 L。相遇时 slow 走了 a+b、fast 走了 2(a+b) 且多绕了若干整圈，推出 $a = (整圈数)\cdot L - b$ 。所以让一个指针从头、另一个从相遇点同速前进，各走 a 步后恰好在入口重逢。这就是为什么相遇后「一个回到表头、同速再走」能精确定位入口。环形缓冲区等工程中的「环上双指针」见应用实例。