前言
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.
简单来说,就是在迭代中检测是否存在环路。迭代是计算机中最基本的一种执行模式,几乎任何程序都需要用到迭代(即循环)。环路检测就是应用在具有迭代结构的程序里,用于检测程序是否会在一个环路中死循环,或是用来检测图、链表或状态机等结构中是否含有环。
所以我们由此得出一个问题:如何判断是否有环,如果有环,环点(环的起点)在哪,环有多长?
算法原理
对于环的判断可以很容易得出一种算法,我们知道在环里绕圈圈必然会重复经过某个节点。所以我们记录下每个节点的信息,当出现节点信息重复的时候,就说明环存在。环点就是第一个检测到重复的节点,那么环长也能基于此计算出来了。
但是这样的算法有个致命的问题,当环非常长时,储存节点的空间开销就逐渐变得不可接受,有没有一种方法能够不记录这么多节点,就能够判断环呢?
所以就出现了我们今天的主角:Floyd’s tortoise and hare
Floyd 很形象的描述了他的算法 Tortoise and Hare,乌龟和兔子。实际上就是快慢指针的一种形象化表示。
那为什么快慢指针能解决这个问题呢,这基于这样一个前提:在环中,快的一方总会追上慢的一方,即在环中相遇。
接下来我们抛开麻烦的数学推导,用几张图形象地进行推理。
推理
首先,我们假设整条链路都是一个环,如下图所示。快慢指针都在起点开始运动(快指针运动速度是慢指针的两倍),那么当慢指针走完一圈时,快指针刚好走了两圈,并且二者恰好在起点相遇。
那么我们加上一条直链会怎么样呢?如下图所示,当快慢指针共同经过一条直链后,从慢指针进入环点的这一刻来看,快指针已经从环点走出了一段距离。
那么再回到我们的圆环模型,我们将环点当作起点,如下图。当他们在起点一起出发时,最终快指针会在起点追上慢指针。而当快慢指针一起经过一段直链之后,快指针多走了一段距离,所以最终快指针会在慢指针回到起点前就追上它。
于是我们得到一个结论:慢指针在环中至多走完一圈就会被快指针追上。
所以我们对于环的判断就变得简单了:
- 如果慢指针与快指针相遇,则存在环,且慢指针最多走完一圈
- 如果慢指针最终走向了某种形式的尽头,则无环(例如链表,无环则最终节点为
null
)
我们确定了存在环,那么环长的判断就简单了:
- 记住当前节点信息,进行计数,最终回到该节点,就可以得到环长
那么环点如何确定呢?这时候需要进行一定的数学推导,但也十分简单。
如下图所示,我们标记三段距离:
- 起点到环点的距离
a
- 慢指针在环内的移动距离
b
- 相遇点到环点的距离
c
假设快指针在环内已经走了 n
圈,那么有关系 a + n*(b+c) + b = 2 * (a+b)
,即快指针路程是慢指针的两倍。
于是有 a = (n-1)(b+c) + c
,也就表明 n-1
圈的环长加上 c
就是环点与起点的距离。实际上也表明慢指针再走过距离 a
,最终会停在环点上(走过 n-1
圈还是在相遇点,再走过距离 c
就到了环点)。
但由于我们不知道圈数是多少,所以也无法确定何时停下来,这时候就需要引入一个辅助节点了。我们让辅助节点和慢指针一起移动,最终他们会在环点相遇(辅助节点走过距离 a
到环点,慢指针走过距离 a
也会停在环点),当他们相遇时,就可以计算出环点距离起点的距离了。
至此我们就解决了关于环的所有问题:
- 判断环是否存在
- 计算环长
- 确认环点