Day 62：链表循环检测

正文

任务是检测和修复包含循环的单链表。解决方案快速，简单，精彩。想法是，使用两个指针（ -慢速指针和快速指针）遍历列表。 慢指针逐节点迭代，而快速指针迭代两个节点。 如果指针相遇，那就是一个循环。

来用一点数学知识，来说清楚算法如何执行。

        代号表示：

        N，元素数量

        C，循环长度

        T = N – C，超出循环长度的元素数量

        K，内循环步数

首先，关注最简单的案例 - 完整周期；尾部直接指向头部的链表，即N = C。在这种情况下算法必须执行的步骤数是多少？ 我们知道快速指针在遇到慢速指针时必须迭代两倍的节点。 这导致了一致性。 

在这些简单的情况下，快慢指针在最后一个元素相遇。如果你细想一下，这是一个直观的结果。但是尾节点指向列表中的任何位置的一般情况呢？ 将T表示为不属于循环的元素数量，并要注意在慢速指针进入循环时的情况。

慢速指针已经做了T步，而快速指针已经做了2T步。 既然它们都处于循环中，那么现在它们必须遵循与以前相同的一致性。

我们知道k是慢速指针进入循环后所做的步数。 等式表示如果我们再做T个步骤，则慢指针在列表中的最后一个元素处终止并结束循环。因此，从头开始另一个缓慢的指针并遍历列表，直到这两个指针相遇。必须修复的位置正是相遇点。

算法

运行