为什么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)

所以，differen指针吨情况如下：

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

前两对增量 - （1,2）和（2,3）工作得很好，但是当我使用的一对（1,3），该算法不似乎在这对工作。是否有一个规则，我们需要增加这个算法的步骤才能保持真实？

虽然我搜索了较慢和较快指针的各种增量步骤，但至今我还没有发现一个相关答案，为什么它不适用于此列表上的增量（1,3）。

Answer 1

如果指针增量与周期长度之间的差异是互质（即它们的最大公约数必须为1），则算法只能保证在任何位置找到一个周期。

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

对于(1,3)，不同的是3-1=2，且周期长度是2，2和2不coprimes，从而该算法不能保证找到循环。

---

理解这一点的关键是，用于检查指针是否曾经达到的目的，至少，在周期内的慢和快球的立场只在乎彼此相对。也就是说，这两个可以被视为等同（两者的区别在于1）

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

因此，我们可以在slow保持恒定的位置而言，并fast在fastIncrement-slowIncrement增量移动想到这一点，在问题变成：

从任何位置开始，我们可以达到某个速度（mod周期长度）移动的特定位置吗？

，或者更一般地说：

我们能达到每一个位置以一定速度（MOD周期长度）移动？

只有当速度和周期长度互反时才会出现这种情况。

例如，看看4的速度和长度为6的周期 - 从0开始，我们访问：
0, 4, 8%6=2, 6%6=0, 4, 2, 0, ... - GCD（4,6）= 2，并且我们只能访问每一第二元件。
要看到这一点，请考虑上面给出的示例的（1,5）（差异= 4）的增量，并看看指针永远不会相遇。 （1,2）增量被认为是算法的基本部分。我应该注意到，据我所知，（1,2）增量被认为是算法的基本部分。

使用不同的增量（按照上面的约束）可能会起作用，但它将远离“官方”算法并涉及更多工作（因为指向链接列表的指针必须迭代增加，在一个步骤中不能增加1以上），对于一般情况没有明显的优势。