algorithm - 使用 Hare 和 Tortoise 方法在链表中进行循环检测

Question

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

Answer 1

这是对非正式证明的尝试。

循环的形状无关紧要。它可以有一个长尾部和一个朝向末端的循环，或者只是一个从头到尾的循环而没有尾部。不管循环的形状如何，有一件事是明确的——乌龟指针追不上兔子指针。如果两者相遇，兔子指针必须从后面追上乌龟指针。

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

1. 兔子指针比乌龟指针慢一步。
2. 兔子指针比乌龟指针落后两步。

所有更大的距离最终都会减少到一或两个。

假设乌龟指针总是先移动(反之亦然)，那么在第一种情况下，乌龟指针向前移动了一步。现在它们之间的距离是 2。当 hare 指针现在走 2 步时，它们将落在同一个节点上。为了更容易理解，这里对同一件事进行了说明。太多的文字会妨碍。

♛ = hare♙ = tortoiseX = 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，这与我们已经证明他们将再一步相遇的第一种情况相同。再次说明，以便于理解。

.♛.♙... #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 步内完成一轮，而兔子在那段时间内可以完成两轮。即使兔子在第一轮中错过了乌龟(它会的)，它肯定会在第二轮中 catch 乌龟。