Floyd、Brent 判圈算法

  本文主要介绍 Floyd 与 Brent 判圈算法及其使用场景,以图解的方式详细描述算法的运行流程,并在文末给出算法的部分应用场景与对应 Leetcode 的题型。

何为判圈算法

根据维基百科的定义,判圈算法是可以在有限状态机、迭代函数或者链表上判断是否存在环,以及求出该环的起点与长度的算法。

也就是说判圈算法能够为我们解决以下三个问题:

  1. 判断链表是否有环
  2. 求环的长度
  3. 确定环的入口

那么它是如何来解决这些问题的?下面通过算法概述这一章节,讲述一下算法的实现原理。

算法概述

Floyd 判圈算法

Floyd 判圈算法的核心原理是,如果存在环,那么从同一个起点(即使这个起点不在某个环上)处,同时开始以不同速度前进的2个指针必定会在某个时刻相遇。

举个简单的例子,下方示例展示了一个不规则的环形链表,。我们给下方示例的运行分为两个阶段:

  1. 第一阶段:相遇阶段,我们设置 Slow、Fast 两个指针,Fast 以 Slow 的两倍速度运行,最终它们会在某个节点相遇。
  2. 第二阶段:寻找环入口阶段,节点相遇后我们将 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 算法无法找到环的入口节点。

应用题

参考资料

推荐阅读