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

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

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

周期的形状无关紧要。它可以有一条长长的尾巴，并有一个向尾的循环，或者只是从头到尾的循环而没有尾巴。不管周期的形状如何，很明显-
乌龟指针无法追赶野兔指针。如果两者碰面，野兔指针必须从后面追赶乌龟指针。

建立了这种可能性后，请考虑以下两种可能性：

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

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

假设乌龟指针始终先移动（也可以相反），然后在第一种情况下，乌龟指针向前移动一步。现在它们之间的距离为2。当野兔指针现在走2步时，它们将降落在同一节点上。这是为便于理解而说明的同一件事。太多的文字会挡住。

♛=野兔♙=乌龟X =都满足..♛♙...＃1-最初，野兔距离乌龟仅一步之遥。..♛.♙..＃2-现在乌龟迈出了一步。现在野兔落后了两步。.... X ..＃3-接下来，野兔走了两步，他们见了面！

现在让我们考虑第二种情况，它们之间的距离为2。慢速指针向前移动一步，它们之间的距离变为3。接下来，快速指针向前移动两步，它们之间的距离减小为1，等于我们已经证明他们将再进一步一步的第一个案例。再次说明，以便于理解。

.♛.♙...＃1-最初，兔子在乌龟后面两步。.♛..♙..＃2-现在，乌龟走了一步，彼此分开了三步。...♛♙..＃3-接下来，野兔分两个步骤进行 *** 作，与之前的情况相同。

现在，关于为什么保证该算法在O（n）中的原因，请使用我们已经确定的野兔在前进之前 会
遇到它的原因。这意味着一旦两者都进入循环中，在乌龟完成另一回合之前，它将遇到野兔，因为野兔的移动速度快两倍。在最坏的情况下，循环将是一个具有n个节点的圆。乌龟只可以n步完成一轮，而野兔在那段时间内可以完成两轮。即使野兔在第一个回合中错过了乌龟（也将会），它也肯定会在第二回合中赶上乌龟。