我在堆栈溢出内外的几篇文章中看到了Floyd算法的几个证明。所有这些都证明了算法的第二部分，即为什么找到循环起点的方法有效。但我见过的所有证明都没有解决第一部分，即为什么慢指针和快指针会在循环内相遇。为什么慢指针和快指针不会无限延伸并且永远不会在特定节点相遇？到目前为止我看到的所有证据要么没有解决这个问题，要么告诉我们“很明显”指针会相遇。很抱歉，但我不明白为什么这些点永远不会无限循环，对我来说，这感觉就像费马最后定理的证明。有人能证明为什么它总是会满足任何长度的循环吗？
。让我们举一个奇数长度链表的例子。
如果将链表循环视为1->2->3->4->5，并且5连接到1（从而形成循环）。现在，让我们有一个来自节点 1 的指针并交替迭代列表。现在访问按以下顺序完成：第一次迭代：1->3->5 接下来从 2 开始。第二次迭代：2->4 接下来从 1 开始...依此类推...
因此，我们可以观察到每个节点都被访问过。即使您从第二个节点开始迭代也是如此。
。偶数长度的第二个示例，1->2->3->4->5->6 & 6->1（循环）。起始节点为1；慢=> 1，快=> 2
慢：1；快：2
慢：2；快：4
慢：3；快：6
慢：4；快：2
慢：5；快：4
慢：6；快：6 => 满足！
因此，在奇数长度的情况下，快遇到慢，因为快接触每个点，而在偶数情况下，慢和快在经过一些迭代后在一个点相遇。
我没有找到类似的证据，只是发布了我的观察结果。 任何建议/更正表示赞赏。 :)
我不确定这个概念是否相似，但两个指针将在循环中相遇这一事实似乎与这个问题相似：
假设三个朋友 A、B、C 分别用 2、4、6 分钟绕完一条封闭路径的外围。他们什么时候再见面？
答案是 LCM(2,4,6) = 12 分钟。我没有具体的数学证明，但我希望它有帮助。