使用 Hare and Tortoise 方法在链表中检测循环 [英] Cycle detection in linked list with the Hare and Tortoise approach

问题描述

我知道为了检测链表中的循环，我可以使用 Hare and Tortoise 方法，该方法包含 2 个指针(慢速指针和快速指针).然而，在阅读维基和其他资源后，我不明白为什么保证两个指针会在 O(n) 时间复杂度内相遇.

解决方案

这是一个非正式证明的尝试.

循环的形状无关紧要.它可以有一个长尾巴，一个循环到最后，或者只是一个没有尾巴的从头到尾的循环.不管周期的形状如何，有一件事是明确的——乌龟指针赶不上兔子指针.两人若有缘相见，野兔指针必须从后面追上乌龟指针.

确定后，考虑两种可能性:

1. 野兔指针比乌龟指针落后一步.
2. 野兔指针比乌龟指针落后两步.

所有更远的距离最终都会减少到一两个.

假设乌龟指针总是先移动(也可以反过来)，那么在第一种情况下，乌龟指针向前移动一步.现在它们之间的距离是2.当兔子指针现在走2步时，它们将落在同一个节点上.为了更容易理解，这里展示了同样的事情.过多的文字会妨碍您.

<前>♛ = 野兔♙ = 乌龟X = 双方相遇..♛♙... #1 - 最初，兔子比乌龟落后一步...♛.♙.. #2 - 现在乌龟迈出了一步.现在野兔落后了两步.....X.. #3 - 接下来，兔子走了两步，他们相遇了！

现在我们考虑第二种情况，它们之间的距离为2，慢指针向前移动一步，它们之间的距离变为3.接下来，快指针向前移动两步，它们之间的距离减少到1与我们已经证明它们将在多一步相遇的第一种情况相同.再次说明，以便于理解.

<前>.♛.♙... #1 - 最初，兔子比乌龟落后两步..♛..♙.. #2 - 现在乌龟迈出一步，它们相距三步....♛♙.. #3 - 接下来，野兔采取与前一个案例相同的两个步骤.

现在，至于为什么该算法保证在 O(n) 中，请使用我们已经确定的内容，即兔子在前进之前将遇到乌龟.这意味着一旦两者都在循环内，在乌龟完成另一轮之前，它将遇到兔子，因为兔子的移动速度是其两倍.在最坏的情况下，循环将是一个有 n 个节点的圆.乌龟只能在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:

1. hare pointer is one step behind the tortoise pointer.
2. hare pointer is two steps behind the tortoise pointer.

All greater distances will reduce to one or two eventually.

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!

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.

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屋！