Floyd、Brent 判圈算法
2020-06-24 Algorithm本文主要介绍 Floyd 与 Brent 判圈算法及其使用场景,以图解的方式详细描述算法的运行流程,并在文末给出算法的部分应用场景与对应 Leetcode 的题型。
何为判圈算法
根据维基百科的定义,判圈算法是可以在有限状态机、迭代函数或者链表上判断是否存在环,以及求出该环的起点与长度的算法。
也就是说判圈算法能够为我们解决以下三个问题:
- 判断链表是否有环
- 求环的长度
- 确定环的入口
那么它是如何来解决这些问题的?下面通过算法概述这一章节,讲述一下算法的实现原理。
算法概述
Floyd 判圈算法
Floyd 判圈算法的核心原理是,如果存在环,那么从同一个起点(即使这个起点不在某个环上)处,同时开始以不同速度前进的2个指针必定会在某个时刻相遇。
举个简单的例子,下方示例展示了一个不规则的环形链表,。我们给下方示例的运行分为两个阶段:
- 第一阶段:相遇阶段,我们设置
Slow、Fast
两个指针,Fast 以 Slow 的两倍速度运行,最终它们会在某个节点相遇。 - 第二阶段:寻找环入口阶段,节点相遇后我们将 Slow 指针重置到链表原点,并且将 Slow、Fast 指针设置为一样的运行速度,它们再次相遇的点即环的入口。
该示例展示了 Floyd 判圈算法寻找链表环形入口的过程,可通过 Next 按钮单步执行,观测算法运行流程。
接下来同学可能会有疑问,为什么这两个阶段结合起来能够找到环状入口?下方我们通过一张图以数学的方式来证明一下该算法,下图来源于环形链表 II - 环形链表 II - 力扣(LeetCode)
我们利用已知的条件:慢指针移动 1 步,快指针移动 2 步,来说明它们相遇在环的入口处。
$$2 * distance(slow) = distance(fast)$$
$$2(F + a) = F + a + b + a$$
$$F = b$$
所以在第一阶段末,只需要归位一个节点并以同样的速度运行,即可在环入口相遇。
Brent 判圈算法
Brent 判圈算法在判断链表是否有环的场景中可以比Floyd更快一点,他的算法原理如下:
该示例展示了 Brent 算法判断链表是否有环的过程,可通过 Next 按钮单步执行,观测算法运行流程。
值得注意的是,Brent 算法无法找到环的入口节点。
应用题
- 141. 环形链表 - 力扣(LeetCode)
- 142. 环形链表 II - 力扣(LeetCode)
- 287. 寻找重复数 - 力扣(LeetCode)
- 160. 相交链表 - 力扣(LeetCode)