使用Hare and Tortoise方法在链表中进行循环检测 [英] Cycle detection in linked list with the Hare and Tortoise approach
问题描述
我知道，为了检测链表中的循环，我可以使用Hare and Tortoise方法，该方法包含2个指针(慢速和快速指针).但是，在阅读了Wiki和其他资源后，我不明白为什么要保证两个指针在O(n)时间复杂度上会合.
I understand that in order to detect a cycle in a linked 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 is it 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.
在建立了该可能性之后，请考虑以下两种可能性:
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.
这篇关于使用Hare and Tortoise方法在链表中进行循环检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
