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

Question

据我所知,为了检测链表中的循环,我可以使用Hare和Tortoise方法,它有2个指针(慢速和快速).但是,在阅读了wiki和其他资源之后,我不明白为什么保证这两个指针在O(n)时间复杂度上会满足.

Answer 1

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

循环的形状无关紧要.它可以有一个长尾巴,一个朝向末端的循环,或者只是一个从开始到结束而没有尾巴的循环.无论循环的形状如何,有一件事是清楚的 - 乌龟指针无法赶上野兔指针.如果两人永远相遇,野兔指针必须从后面赶上乌龟指针.

有了这个,考虑两个可能性:

1. 野兔指针是乌龟指针背后的一步.
2. 野兔指针是乌龟指针背后的两步.

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

假设乌龟指针总是先移动(也可能是另一种方式),那么在第一种情况下,乌龟指针向前迈出一步.现在它们之间的距离是2.当野兔指针现在采取两步时,它们将落在同一节点上.这是为了便于理解而说明的相同内容.太多的文字可能会妨碍.

? = 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,这与我们已经证明他们将再一次见面的第一个案例.再次,说明为了更容易理解.

.?.?... #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个步骤中完成一轮,但野兔在那段时间内可以完成两轮.即使野兔在第一轮(它将会)错过了乌龟,它肯定会在第二轮赶上乌龟.