弗洛伊德的周期检测算法|确定周期的起点

Question

我正在寻求帮助了解弗洛伊德的周期检测算法。我经历了关于维基百科的解释（http://en.wikipedia.org/wiki/cycle_detection#tortoise_and_hare)

我可以看到该算法如何在O（n）时间中检测周期。但是，我无法想象一个事实，即一旦乌龟和野兔指针第一次相遇，就可以通过将乌龟指针移回开始，然后一次移动乌龟和野兔一次。他们第一次见面的点是周期的开始。

我无法理解/可视化它，可以通过提供与维基百科上的解释相比提供的解释来提供帮助吗？

Answer 1

我在Stackoverflow上找到了答案。感谢有人为我调查。对于那些喜欢我的人想要解释，请参考： https://stackoverflow.com/questions/3952805/proof-of-detecting-the-prof-the-start-of-cycle-in-link-link-list 对问题的选择答案，解释了！

Answer 2

你可以参考 “检测单个链接列表中循环的开始”, ，这是一个摘录：

距离旅行 slowPointer 开会前 $ = x+y $

距离旅行 fastPointer 开会前 $ =（x + y + z） + y $ = x + 2y + z

自从 fastPointer 与之旅行 双倍的 速度 slowPointer, ， 和 时间是恒定的 对于达到聚会点时。因此，通过使用简单的速度，时间和距离关系（slowPointer 走了一半的距离）：

begin {align*} 2* operatorName {dist}（ text {slowpointer}） 2x+2y＆= x+2y+z x＆= z end {align*}

因此，通过移动 slowPointer 开始链接列表，并将两者兼有 slowPointer 和 fastPointer 一次移动一个节点， 他们俩都有相同的距离.

它们将在循环启动的点上到达链接列表。

Answer 3

我也将公认的答案视为其他地方的证明。但是，虽然很容易抓住，但这是不正确的。它证明的是

$ x = z $（这显然是错误的，并且该图仅使其看起来很合理）。

您真正要证明的是（使用与上面接受答案中图中所述相同的变量）：

$ z = x mod （y + z）$

$（y + z）$是循环长度，$ l $

因此，我们要证明的是：

$ z = x mod l $

或Z与X（Modulo l）一致

以下证明对我更有意义：

会议点，$ m = x + y $

$ 2（x + y）= m + kl $，其中$ k $有些常数。基本上，快速指针旅行的距离为$ x + y $，加上一些循环长度，$ l $

$ x + y = kl $

$ x = kl- y $

上面的方程式证明$ x $与环路长度的某些倍数相同，$ l $减去$ y $。因此，如果快速指针从会议点开始，$ m $或$ x + y $，则最终将在循环开始时。