0%

Floyd 环形算法

题目来自 leetcode 142. 环形链表 II,判断一个链表是否有环,如果有,找到环形起点。

首先是链表判断是否有环,刷过题的都知道快慢指针,快指针一次移动两步,慢指针一次移动一步,如果两个指针最终相遇则有环,如果快指针到达终点,则无环。

计算环形起点一般使用 Floyld 算法。接上面,两指针相遇之后,将慢指针移动到链表头部,然后两个指针每次移动一步,再次相遇就是环形起点。这个算法简洁明了,非常简单,但是需要思考一下证明方法。

假设链表头到环形起点的距离是 $m$,也就是非环部分;链表环长度为 $n$;相遇的时候距离环形起点的位置为 $k$。

慢指针相遇的时候移动距离:$m + A \cdot n + k$,快指针相遇的时候移动距离:$m + B \cdot n + k$。

因为快指针是慢指针的二倍,因此:

$B$ 和 $A$ 都是正整数,因此相遇时慢指针移动的总长度是环形的整倍数,快指针是慢指针的 2 倍,因此快指针走过的总长度也是环形的整倍数。

现在把慢指针移动到链表头部,然后移动 $m$ 步,到达了环形的起点,慢指针移动 $S + m$,快指针移动 $2 \cdot S + m$,$S$ 是环形长度的整倍数,因此快指针此时也一定是到达了环形的起点,两个指针相遇。