Floyd链表环检测算法：快慢指针必相遇的证明请求

前提定义 #

• 设链表非环部分长度为L（从表头到环起点的节点数）
• 环的长度为C（环上的节点总数）
• 慢指针每次移动1步，快指针每次移动2步

第一步：慢指针进入环时的状态 #

慢指针走到环起点需要L步，此时快指针已经移动了2L步。由于快指针早于慢指针进入环，它在环内的位置为：
(2L - L) mod C = L mod C
记这个位置为k，其中0 ≤ k < C。

第二步：环内的追赶与相遇证明 #

此时慢指针位于环起点（位置0），快指针位于环内位置k。我们需要找到一个非负整数n，使得两者移动n步后位置相同：

• 慢指针移动n步后的位置：(0 + n) mod C
• 快指针移动n步后的位置：(k + 2n) mod C

令两者位置相等，可得等式：
n ≡ k + 2n (mod C)
整理后：
0 ≡ k + n (mod C)
即：
n ≡ -k (mod C)

由于0 ≤ k < C，当k≠0时，n = C - k就是满足条件的步数：

• 慢指针位置：(C - k) mod C = C - k
• 快指针位置：(k + 2*(C - k)) mod C = (2C - k) mod C = C - k

两者位置完全重合，实现相遇。

若k=0（即L是C的倍数，慢指针进环时快指针也恰好位于环起点），则两者直接相遇，无需追赶。

为什么不会无限循环？ #

n = C - k是一个有限的正整数（最大为C），意味着最多经过C步，慢指针就会追上快指针。每一轮移动中，快指针相对于慢指针的环内相对距离都会逐步缩小，最终必然归为0，不存在永远追不上的情况。

举个实际例子：

• 环长度C=5，k=3（慢进环时快在环内第3位）
• n=5-3=2步后：慢指针走到位置2，快指针从3→0→2，两者相遇。

内容的提问来源于stack exchange，提问作者Adeeb HS