Floyd 判圈算法

定义

Floyd 判圈算法(Floyd's Cycle Detection),常称"龟兔赛跑"算法,归于 Robert Floyd 名下,用于检测链表或函数迭代序列中是否存在环,并可进一步求出环的起点与长度,空间复杂度仅 O(1)。

原理

设置慢指针每次走一步、快指针每次走两步。若存在环,两指针必在环内相遇;若快指针到达终点则无环。相遇后把其中一个指针移回起点,两指针改为同速前进,再次相遇处即为入环点,这一结论可由相遇时的路程关系推出。让一个指针绕环一圈即可测得环长。

应用

链表成环检测(LeetCode 141/142)、伪随机数序列周期分析、Pollard rho 整数分解算法中的循环检测、重复数查找(把数组值视作指针)等。

对比

Brent 判圈算法采用倍增步长策略,平均比 Floyd 更少的迭代次数;哈希表法思路更直白但需要 O(n) 空间。