algorithm - 为什么 Floyd 的循环查找算法对于某些指针增量速度会失败？

Question

考虑以下链表:

1->2->3->4->5->6->7->8->9->4->...->9->4.....

上面的列表有一个循环如下:

[4->5->6->7->8->9->4]

在白板上绘制链表，我尝试手动求解不同的指针步骤，看看指针如何移动 -

(slow_pointer_increment, fast_pointer_increment)

因此，针对不同情况的指针如下:

(1,2), (2,3), (1,3)

前两对增量 - (1,2) 和 (2,3) 工作正常，但当我使用对 (1,3) 时，算法似乎不适用于这一对。是否有关于我们需要增加多少步数才能使该算法成立的规则？

虽然我搜索了较慢和较快指针的各种增量步骤，但到目前为止我还没有找到一个相关的答案来说明为什么它不适用于此列表中的增量 (1,3)。

Answer 1

如果指针增量和循环长度之间的差是互素数(即它们的最大公约数必须为 1)，则可以很容易地证明该算法保证找到从任何位置开始的循环。

对于一般情况，这意味着增量之间的差值必须为 1(因为这是唯一与所有其他正整数互质的正整数)。

对于任何给定的指针增量，如果值不是互质，它仍然可以保证找到一个循环，但是需要想出一种不同的方法来证明它会找到一个循环。

题中的例子，指针递增(1,3)，相差3-1=2，循环长度为6。 2 和6 不是互素数，因此不知道该算法是否能保证在一般情况下找到循环。看起来确实可以保证找到循环(包括问题中的示例)，即使它没有到达每个位置(适用于互质，如下所述)，但我没有目前对此进行证明。

---

理解这一点的关键是，至少为了检查指针是否相遇的目的，循环中慢指针和快指针的位置仅相互关联。即这两个可以认为是等价的:(两者相差1)

slow fast             slow fast
   ↓ ↓                   ↓ ↓
 0→1→2→3→4→5→0     0→1→2→3→4→5→0

所以我们可以根据 slow 的位置保持不变和 fast 以 fastIncrement-slowIncrement 的增量移动来考虑这一点，此时问题变成了:

Starting at any position, can we reach a specific position moving at some speed (mod cycle length)?

或者，更一般地说:

Can we reach every position moving at some speed (mod cycle length)?

只有当速度和周期长度互质时才会成立。

例如，看速度为4，循环长度为6——从0开始，我们访问:
0, 4, 8%6=2, 6%6=0, 4, 2, 0, ... - GCD(4,6) = 2，我们只能访问每隔一个元素.
要查看实际效果，请考虑上面给出的示例的 (1,5)(差 = 4)增量，并查看指针永远不会相遇。

---

我应该指出，至少据我所知，(1,2) 增量被认为是算法的基本部分。

使用不同的增量(根据上述约束)可能会奏效，但这将偏离“官方”算法，并且会涉及更多工作(因为指向链表的指针必须迭代递增，您可以'在单个步骤中将其增加超过 1)对于一般情况没有任何明显的优势。