为什么在链表中查找循环时将指针增加 2，而不是 3、4、5？

我看了一下question https://stackoverflow.com/questions/2663115/interview-question-how-to-detect-a-loop-in-a-linked-list已经讨论了在链表中查找循环的算法。我读过了Floyd 的环路查找算法 http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare解决方案，在很多地方提到我们必须采用两个指针。一个指针（slower/tortoise）加1，另一个指针（faster/hare）加2。当它们相等时，我们发现循环，如果faster指针达到空，则链表中没有循环。

现在我的问题是为什么我们将更快的指针增加 2。为什么不做其他的事情呢？需要增加 2，或者我们可以将其增加 X 以获得结果。如果我们将 Faster 指针增加 2，是否有必要找到循环，或者可能存在需要增加 3、5 或 x 的情况。

从正确性的角度来看，没有理由需要使用数字 2。任何步长的选择都可以（当然，除了一个）。然而，选择大小为 2 的步长可以最大限度地提高效率。

To see this, let's take a look at why Floyd's algorithm works in the first place. The idea is to think about the sequence x₀, x₁, x₂, ..., x_n, ... of the elements of the linked list that you'll visit if you start at the beginning of the list and then keep on walking down it until you reach the end. If the list does not contain a cycle, then all these values are distinct. If it does contain a cycle, though, then this sequence will repeat endlessly.

以下是弗洛伊德算法发挥作用的定理：

The linked list contains a cycle if and only if there is a positive integer j such that for any positive integer k, x_j = x_jk.

Let's go prove this; it's not that hard. For the "if" case, if such a j exists, pick k = 2. Then we have that for some positive j, x_j = x_2j and j ≠ 2j, and so the list contains a cycle.

For the other direction, assume that the list contains a cycle of length l starting at position s. Let j be the smallest multiple of l greater than s. Then for any k, if we consider x_j and x_jk, since j is a multiple of the loop length, we can think of x_jk as the element formed by starting at position j in the list, then taking j steps k-1 times. But each of these times you take j steps, you end up right back where you started in the list because j is a multiple of the loop length. Consequently, x_j = x_jk.

This proof guarantees you that if you take any constant number of steps on each iteration, you will indeed hit the slow pointer. More precisely, if you're taking k steps on each iteration, then you will eventually find the points x_j and x_kj and will detect the cycle. Intuitively, people tend to pick k = 2 to minimize the runtime, since you take the fewest number of steps on each iteration.

我们可以更正式地分析运行时，如下所示。如果列表不包含循环，则快速指针将在 n 步后到达列表末尾，时间复杂度为 O(n)，其中 n 是列表中元素的数量。否则，当慢指针走了j步后，两个指针就会相遇。请记住，j 是 l 大于 s 的最小倍数。如果 s ≤ l，则 j = l；否则，如果 s > l，则 j 最多为 2s，因此 j 的值为 O(s + l)。由于 l 和 s 不能大于列表中的元素数量，这意味着 j = O(n)。然而，在慢速指针走了 j 步之后，对于慢速指针所采取的 j 步，快指针将采取 k 步，因此它将采取 O(kj) 步。由于 j = O(n)，因此净运行时间至多为 O(nk)。请注意，这表示我们使用快速指针执行的步骤越多，算法完成所需的时间就越长（尽管只是成比例）。因此选择 k = 2 可以最大限度地减少算法的整体运行时间。

希望这可以帮助！