判断单向链表是否有环及求环入口的算法数学证明

由于该博客所使用的图床需要一个备过案的域名,所以博客中的图片都暂时失效。读者可以移步知乎专栏阅读:

知乎

关于图床问题我会尽快解决,谢谢支持。

读者您好:本篇文章未经作者本人授权,禁止任何形式的转载,谢谢!**

概要

本篇文章,主要讲解 title 中所描述算法的原理及数学证明。需要注意的是,本篇中出现的代码未必是完整代码,可能只是一个关键代码块,且采用 C++ 编写。

判断链表是否有环

当单向链表中存在环的时候,遍历此链表会发生无限循环,无法到达末尾(实际上并没有末尾)的情况,所以在可能发生这种情况的时候,需要检查链表中是否存在一个环。

算法

算法很简单,设置两个指针,分别为快指针(fast)和慢指针(slow),快指针每次向前走两步,慢指针每次走一步。如果快指针指向了 NULL,那么说明此链表中没有坏,因为有环会发生无限循环,不可能走到末尾。而在有环的情况下,两个指针会在环里绕圈,最终指向同一个地址,即两个指针相遇,根据这个就可以终止遍历代码且证实链表有环。

附上关键代码:

1
2
3
4
5
6
7
8
9
10
ListNode *slow = head->next;
ListNode *fast = slow->next;
while (fast && slow != fast)
{
slow = slow->next;
fast = fast->next ? fast->next->next : NULL;
}
return fast ? true : false;

有环时两个指针一定会相遇的数学证明

在做这道题的时候可能会有疑惑:为什么在有环的时候两个指针一定会相遇?这里给出数学证明。

当 slow 指针一步步走到环的入口时(注意此时 fast 已经在环里了,因为它比 slow 要快),设:

  • 链表头指针 head 到链表环的入口处的距离为 $ L_1 $
  • fast 指针距离环的入口的距离为 $ L_2 $
  • fast 已经在环内走了 $ N_1 $ 圈(向下取整)
  • 假设 slow 再经过 $ i $ 步与 fast 相遇
  • 环的周长为 $ C $
  • fast 和 slow 走过的总路程分别为 $ disFast $ 和 $ disSlow $

示意图如下:

示意图

则当 slow 走到环入口时,可得知:

又因为 fast 每次走两步,即比 slow 快一倍,所以 若两个指针相遇,则有:

减去 $ L_1 $ 是为了减掉不在环内的长度从而求得相遇点相对于环入口的距离,由于等式两边的值实际上是相对于环入口的距离,所以有:

可以看到, $L_2$ 和 $i$ 总和等于环的周长的整数倍,这个等式是成立的,实际上我们也求出了 $i$ 的值。结合图和最终的等式,我们可以看到,对于任意 $L_2$ ,都可以求出无数个 $i$ 值,每个值都对应一个周长的整数倍,而对于每一个 $i$ 值,最终相遇的位置都一样,这也很好理解,当 $slow$ 和 $fast$ 相遇后,由于 2 倍速度的关系,当 $slow$ 继续走半圈的时候,$fast$ 走了一圈回到了之前的相遇点,当 $slow$ 再走半圈回到之前的相遇点, $fast$ 又走了一圈再次回到之前的相遇点。

这就是对于在有环的单链表中快慢指针一定会相遇的数学证明。

求环的入口

在上一个问题之后,还有一个相关的问题,即如果此链表有环,求环的入口节点。直接想此算法可能比较难解,所以这个问题可以尝试着从数学上入手。

数学

(注意与上一个问题所表示的含义可能有不同)

  • $ L_1 $ 为链表头 head 到环入口的距离
  • $ L_2 $ 为从环入口向前到相遇点的距离
  • $ L_3 $ 为从相遇点向前到环入口的距离 (按照指针前进的方向计算)
  • $ C $ 为环的周长
  • $ N_1 $ 和 $ N_2 $ 分别为 slow 和 fast 在相遇时走过的圈数(向下取整)
  • $ disSlow $ 和 $ disFast $ 分别为 slow 和 fast 在相遇时走过的距离

示意图如下:

示意图

则:

又因为 fast 速度是 slow 的 $ 2 $ 倍,所以:

因为 $fast$ 的速度是 $slow$ 的两倍,所以 $N_2$ 至少是 $N_1$ 的两倍(至少而不是恰好是因为 $fast$ 进入环时 $slow$ 可能还没进入环,所以 $fast$ 可能会先在环内走几圈),

这里其实还可以求出的是,当 $N_2$ 等于 2 倍的 $N_1$ 的时候,$L_1$ 和 $L_2$ 都为 0 ,也就是整个链表就是一个环 。

由此可以看出,$ L_1 $ 即链表头 head 到环入口的距离就等于 $(N_2 - 2N_1)C - L_2$,其实就等于 $L_3 + (N_2 - 2N_1 - 1)C$ (注意 $L_3$ 是按照指针前进方向算的,并不是最小距离,所以这个结果对于整个链表都是环也是有效的) ,而从相遇点向前走 $L_3 + (N_2 - 2N_1 - 1)C$ 的距离,正好就走到了环的入口(如果没理解可以在图上比划一下即可),所以我们就可以推导出算法,即:让两个指针其中一个从链表头 head 出发,一次走一步,让另一个指针从相遇点出发,也一次走一步,相遇点就是环的入口。

算法

关键代码如下:

1
2
3
4
5
6
7
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}

注意事项

这里有一个小坑,在算法的最最开始,可以让 slow 和 fast 都为 head 指针,或者 slow 为 head 的下一个节点,fast 为下两个节点。如果让 slow 为 head 指针,fast 为下一个节点,则可能无法求出环的入口,甚至可能陷入死循环。但对于第一个问题,这个步骤没有影响。

坚持原创技术分享,您的支持将鼓励我继续创作!