Floyd循环检测算法中循环起点定位的原理疑问

先明确几个已知条件和推导结论：

• 慢指针（tortoise）每次走1步，快指针（hare）每次走2步，相遇时慢指针走了k步，快指针走了2k步
• 非循环段长度为x，循环周长为p，相遇点距循环起点的距离为y
• 推导得出：k是p的整数倍（因为快指针比慢指针多走的步数是循环周长的整数倍，即2k - k = k = t*p，t为正整数）
• 同时，慢指针的k步可拆解为：k = x + y + m*p（m是慢指针在循环内绕的圈数）

核心推导：为何同速走x步后慢指针到循环起点？ #

把k = t*p代入k = x + y + m*p，整理可得：

x + y + m*p = t*p
x = (t - m)*p - y

现在看两者走x步后的位置：

• 快指针：从起点出发走x步，刚好走完非循环段，直接到达循环起点（位置为x）。
• 慢指针：相遇时的位置是x + y（走完非循环段后在循环内走了y步）。再走x步后，总位置为：

  (x + y) + x = x + (x + y)
  

  代入x + y = (t - m)*p（从上面的等式变形而来），慢指针的最终位置就是x + (t - m)*p——相当于从循环起点出发绕了(t - m)整圈，最终必然回到循环起点。

简单说：相遇时慢指针在循环内还差p - y步回到起点，而x刚好等于(t - m)圈循环加上p - y步，所以走x步后刚好绕回循环起点；同时快指针走x步刚好到起点，两者就此相遇在循环起点。

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