为什么在链表中find循环的时候为什么不用3,4,5？
我已经看了一个关于在链表中find循环的algorithm的问题 。 我已经阅读了弗洛伊德的循环发现algorithm解决scheme，在很多地方提到我们必须采取两个指针。 一个指针（慢/龟）增加一个，其他指针（更快/更多）增加2.当它们相等时，我们find循环，如果更快的指针变为空，则链表中没有循环。
现在我的问题是为什么我们增加了更快的指针2.为什么不是别的？ 增加2是必要的，或者我们可以通过增加X来得到结果。 如果我们用2递增更快的指针，或者可能出现需要增加3或5或x的情况，是否有必要find循环。
没有理由需要使用二号。 步长的任何select都可以工作（当然除外）。
要明白为什么这个工作，让我们来看看为什么弗洛伊德的algorithm首先工作。 这个想法是考虑如果从列表的开始处开始，将要访问的链表的序列x 0 ，x 1 ，x 2 ，…，x n ，…继续走下去，直到你到达最后。 如果列表不包含循环，则所有这些值都是不同的。 如果它确实包含一个循环，那么这个序列会不断重复。
下面是使Floydalgorithm工作的定理：
当且仅当存在正整数j，使得对于任何正整数k，x j = x jk ，链表包含循环。
我们去certificate一下吧 这并不难。 对于“if”的情况，如果存在这样的aj，则selectk = 2。然后我们有一个正j，x j = x 2j和j≠2j，所以列表包含一个循环。
对于另一个方向，假定列表包含从位置s开始的长度l的循环。 设j是大于s的l的最小倍数。 那么对于任意的k，如果我们考虑x j和x jk ，由于j是循环长度的倍数，我们可以把x jk看作从列表中的位置j开始形成的元素，然后取j步骤k-1倍。 但是这些时候你每走j步，最后就会回到你开始列表的位置，因为j是循环长度的倍数。 因此，x j = x jk 。
这个certificate保证你，如果你在每次迭代中采取任何不变的步骤，你确实会碰到慢指针。 更确切地说，如果你在每次迭代中采取k步，那么你将最终find点x j和x kj，并且将检测周期。 直觉上，人们倾向于selectk = 2来最小化运行时间，因为在每次迭代中采取的步数最less。
我们可以更正式地分析运行时间如下。 如果列表不包含循环，则快速指针将在O（n）时间n步后到达列表的末尾，其中n是列表中元素的数量。 否则，两个指针在慢指针执行j个步骤之后会相遇。 请记住，j是大于s的l的最小倍数。 如果s≤1，那么j = 1; 否则如果s> 1，那么j将最多2s，所以j的值是O（s + l）。 由于l和s不能大于列表中元素的数量，所以这意味着比j = O（n）。 然而，在慢指针执行了j个步骤之后，快指针对于较慢指针所采取的j个步骤中的每一个都将采取k个步骤，所以它将采取O（kj）个步骤。 由于j = O（n），净运行时间最多为O（nk）。 请注意，这说明我们用快速指针执行的步骤越多，algorithm完成的时间越长（尽pipe只是按比例）。 selectk = 2因此使algorithm的整体运行时间最小化。
希望这可以帮助！
让我们假设不包含循环的列表长度为s，循环长度为t，fast_pointer_speed与slow_pointer_speed的比值为k。
让两个指针从循环开始的距离j相遇。
所以，距离慢的指针行进= s + j。 快速指针行进距离= s + j + m * t。 但是，快速指针也将行进距离k *（s + j）（k倍慢速指针的距离）。
因此，我们得到k *（s + j）= s + j + m * t。
s + j =（m / k-1）t。
因此，从上面的等式，慢指针传播的长度是循环长度的整数倍。
为了获得最大效率，（m / k-1）= 1（慢指针不应该多次循环）。
因此，m = k-1 => k = m + 1
由于m是快速指针完成循环的次数，m> = 1。 为了最大效率，m = 1。
因此k = 2。
如果我们取k> 2的值，那么两个指针必须行进的距离就越多。
希望以上解释有帮助。
考虑一个大小为L的循环，意味着第k个元素是循环的地方：x k – > x k + 1 – > …> x k + L-1 – > x k 。 假设一个指针以r 1 = 1的速率运行，另一个在r 2运行 。 当第一个指针到达x k时 ，第二个指针已经在某个元素x k + s的循环中，其中0 <= s <L。在m个指针增加后，第一个指针位于x k +（m mod L）第二指针在x k +（（m * r 2 + s）mod L） 。 因此，两个指针碰撞的条件可以表示为满足同余的m的存在
m = m * r 2 + s（mod L）
这可以通过以下步骤简化
m（1-r 2 ）= s（mod L）
m（L + 1-r 2 ）= s（mod L）
这是线性一致的forms。 如果s被gcd（L + 1-r 2 ，L）整除，则它有一个解m。 如果gcd（L + 1-r 2 ，L）= 1，肯定会是这种情况。 如果r 2 = 2，则gcd（L + 1-r 2 ，L）= gcd（L-1，L）= 1并且解m总是存在。
因此，对于任何周期长度L，r 2 = 2具有良好的性质，它满足gcd（L + 1-r 2 ，L）= 1，从而保证即使两个指针在不同位置开始，指针也将最终碰撞。 其他的r 2值没有这个属性。
如果快速指针在1步移动3步和慢指针，则不能保证两个指针在包含偶数个节点的循环中相遇。 如果慢速指针移动2步，会议将得到保证。
一般来说， 如果兔子以H移动，而龟以T移动，则如果H = T + 1 ，则保证在一个循环中相遇。
考虑兔子相对于乌龟的移动。
- 兔子相对于龟的速度是每次迭代
H - T节点。 -
给定一个长度为
N =(H - T) * k的周期，其中k是任何正整数，野兔会跳过每个H - T - 1节点（再次，相对于龟），这将是不可能的如果乌龟在这些节点中的任何一个遇见。 -
会议保证的唯一可能性是当
H - T - 1 = 0。
因此，只要慢速指针增加x - 1 ，就允许增加快速指针x 。
如果链表有一个循环，那么一个增量为2的快速指针会更好，然后说3或4或更多的增量，因为它确保了一旦我们在循环内部，指针肯定会碰撞，并且不会有超车。
例如，如果我们增加3，并在循环内部假设
fast pointer --> i slow --> i+1 the next iteration fast pointer --> i+3 slow --> i+2
而这种情况将不会发生，增加2。
同样，如果你真的不幸，那么你可能会在循环长度为L的情况下结束，并且将快速指针递增L+1 。 那么你将无限地卡住，因为运动的快慢指针的差别总是L
我希望我自己清楚。
