Floyd 判圈算法

2017-12-01

判断一个单链表中是否存在环,并找出环的入口: https://leetcode.com/problems/linked-list-cycle-ii/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

不知道 LeetCode 难度评级的标准是什么,有的 hard 题看完题目就有思路,像这种 medium 题我琢磨半天也想不出空间复杂度为 $O(1)$ 的解法。后来了解到这一题已经有著名的解法了,即 Floyd 判圈算法,没错,就是求最短路径的弗洛伊德算法的那个 Floyd。

哈希表法

时间复杂度 $O(n)$,空间复杂度 $O(n)$。略。

Floyd 判圈算法

在一个环中,如果两人速度不等且保持不变,那么总有一个时刻两者会相遇。应用此技巧,让一个slow指针每次移动一个结点,fast指针每次移动两个结点,如果两者最终能相遇,则说明单链表中存在环,如果fast走到了表尾,则说明不存在。

如果要求环长也好办,当两者相遇时,让其中一人保持不动,另一人再移动一圈,再次相遇时移动的路程即为环长。

但如何求出环的入口呢?

现已知单链表中存在环,设头结点与环入口距离为 $a$,从环入口到相遇结点的距离为 $b$,环长度为 $r$,slow指针在相遇前已经在环中移动了 $n_1$ 圈,fast指针在相遇前已经在环中移动了 $n_2$ 圈,那么slow指针移动的总路程为 $$s_1 = a + n_1r + b$$

fast指针移动的总路程为 $$s_2 = a + n_2r + b$$

由于fast移动速度为slow的两倍,路程也为两倍,则 $s_2 = 2s_1$,两式相减得 $$s_2 - s_1 = s_1 = (n_2 - n_1)r$$

这说明slowfast指针移动路程都为环长的整数倍。

现增设一个指针slow1,让其从头结点开始,每次移动一个结点,与相遇结点处的slow指针同时出发。当slow1移动到环的入口,即距离为 $a$ 时,slow移动的距离为 $$s_1' = s_1 + a$$

slow指针也一定停留在环的入口,它可以看作先移动了距离 $a$,即环入口处,又绕环移动了若干圈。

这说明,当slowslow1相遇时,相遇结点必定为环的入口。

时间复杂度 $O(n)$,空间复杂度 $O(1)$。

实现源码

https://github.com/qianbinbin/leetcode

LeetCode算法
本站的全部文字在署名-非商业性使用-相同方式共享 4.0 国际协议之条款下提供。

交换 Android 手机的返回键和最近任务键

Single Number II