据我所知，为了检测周期在列表中，我可以用龟兔赛跑的方法，其中包含两个指针（慢速和快速的）。然而，阅读维基和其他资源后，我不明白为什么它是保证这两个指针会为O满足（n）的时间复杂度...

I understand that in order to detect a cycle in a list I can use the Hare and Tortoise approach, which holds 2 pointers (slow and fast ones). However, after reading in Wiki and other resources, I do not understand why it is guaranteed that the two pointers will meet in O(n) time complexity...

推荐答案

下面是在一个非正式的证据的一种尝试。

Here's an attempt at an informal proof.

周期的形状并不重要。它可以有一个长尾巴，并且朝向端部的环，或者仅仅一个循环从开始到结束没有尾巴。不考虑周期的形状，有一点是清楚的 - 那乌龟指针不能赶上野兔指针。如果两个人永远满足，野兔指针已经赶上了从后面龟指针。

The shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end, or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the tortoise pointer can not catch up to the hare pointer. If the two were ever to meet, the hare pointer has to catch up the to tortoise pointer from behind.

通过所建立，考虑两个possibilites：

With that established, consider the two possibilites:

所有更远的距离将缩短至一到两个最终。

All greater distances will reduce to one or two eventually.

假设乌龟指针总是先走（可以是倒过来也行），然后在第一种情况下，乌龟指针会向前迈进一步。现在，它们之间的距离为2。当兔子指针需要2步现在，他们将土地在同一节点上。下面是说明为了便于理解同样的事情。太多的文字可以得到的方式。

Assuming the tortoise pointer always moves first (can be the other way around too), then in the first case, the tortoise pointer takes one step forward. Now the distance between them is 2. When the hare pointer takes 2 steps now, they will land on the same node. Here's the same thing illustrated for easier understanding. Too much text can get in the way.

♛ = hare
♙ = tortoise
X = both meet

..♛♙... #1 - Initially, the hare is one step behind the tortoise.
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind.
....X.. #3 - Next, the hare takes two steps and they meet!

现在让我们考虑第二壳体，其中它们之间的距离为2。缓慢指针移动一步向前和它们之间的距离变得3.接着，快指针向前移动两步和它们之间的距离减少到1，其是相同的，我们已经证明了，他们将在一个步骤符合第一种情况。再次，说明更容易理解。

Now let's consider the second case where the distance between them is 2. The slow pointer moves one step forward and the distance between them becomes 3. Next, the fast pointer moves forward two steps and the distance between them reduces to 1 which is identical to the first case in which we have already proved that they will meet in one more step. Again, illustrated for easier understanding.

.♛.♙... #1 - Initially, the hare is two steps behind the tortoise.
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart.
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case.

现在，至于为什么这个算法是保证在O（n）的，使用什么我们已经建立了，兔子的会符合乌龟就向前推进了。这意味着一旦两者都是内循环，乌龟完成了又一轮之前，将满足野兔，因为野兔动作快两倍。在最坏的情况下，该循环将与n个节点的圆。虽然乌龟只能完成一个回合在n步，野兔可以完成两轮在这段时间。即使野兔错过了第一轮的乌龟（它将），它肯定会赶上在第二轮的乌龟。

Now, as to why this algorithm is guaranteed to be in O(n), use what we've already established that the hare will meet the tortoise before it moves ahead. Which means that once both are inside the loop, before the tortoise completes another round, it will meet the hare since the hare moves twice as fast. In the worst case, the loop will be a circle with n nodes. While the tortoise can only complete one round in n steps, the hare can complete two rounds in that time. Even if the hare missed the tortoise in its first round (which it will), it's definitely going to catch up to the tortoise in its second round.