判断单链表是否有环、求环长和环入口最优算法

优雅的算法 TOMORROW 2个月前 (10-11) 211次浏览 0个评论 扫描二维码
文章目录[隐藏]

判断单链表是否有环是一个十分经典的算法问题,许多考试或者面试都有很大的几率出现。如果事先对此没有一定的理解,临场发挥可能就比较困难了。

 

判断链表是否有环

  • 首先定义两个指针 slow 和 fast,初始都指向链表头指针 head;
  • 然后,slow 每走一步(每次移动一个节点),fast 走两步(移动两个节点);
  • 如果 fast 遇到了 NULL,则链表不存在环;
  • 如果 slow==fast,则链表存在环;

判断单链表是否有环、求环长和环入口最优算法

为什么 slow==fast 就一定会存在环呢?

因为,如果存在环,fast 和 slow 肯定会先后进入环;

当 slow 刚好进入环时,fast 肯定已经在环内的某一个位置了;

而又因 fast 走的速度是 slow 的两倍,所以在 slow 在环内遍历一遍的过程中,fast 指针必然会与 slow 相遇。

其实两个指针就像是两个人在田径场上跑步,一个人的速度是另一个人速度的两倍。无论两个人的起点在何处,慢的人跑完一圈,快的人必然跑完两圈,所以他们必然相遇过。

 

复杂度分析

 

链表长度为 n,显然时间复杂度为 O(n);

空间复杂度为 O(1)。

 

求环的长度

 

上面已经可以判断出是否有环了,如果有环,那么环的长度又是多少呢?该怎么求?

 

这就很简单了,前面已经将环判断出来了,所找到的 slow 和 fast 相遇点必然是在环内的,记录该节点;

所以此时只需用一个指针 p 继续一步步遍历链表,并计数,直到指针 p 重新指向上面的相遇节点,此时计数的值就为环长了。

 

复杂度分析

 

设链表长度为 n,环长为 r 。

如果是在知道一个环内节点的情况下,那么时间复杂度为 O(r),空间复杂度为 O(1);

如果是在不知道是否有环的情况下,那么时间复杂度为 O(n+r),空间复杂度为 O(1)。

 

求环的入口

 

前面已经判断出是否有环了,并求出了环的长度,此时求环的入口也变得很简单了。

  • 定义两个指针 p 和 q,初始指向链表头指针 Head;
  • q 首先移动 r 个节点(r 为环的节点数),p 不动;
  • 然后 p 和 q 一起每次移动一个节点;
  • 直到 p==q,此时 p 和 q 指向的就是环的入口了;

这个应该很容易理解吧,q 比 p 先走了一个环的长度,所以当 p 刚好走到环的入口时,q 就刚刚好遍历了环一遍。

 

复杂度分析

 

设链表长度为 n,环长为 r 。

如果是在知道一个环长度的情况下,那么时间复杂度为 O(n),空间复杂度为 O(1);

如果是在不知道环长度的情况下,那么时间复杂度为 O(n+r+n)= O(n+r),空间复杂度为 O(1)。

 

求链表的长度

 

链表长度 = 头结点到环入口节点的长度 + 环长度 

所以此时,只需用一个指针从头遍历链表节点并计数,求出头结点到环入口节点的长度即可。

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:判断单链表是否有环、求环长和环入口最优算法
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
自然的树叶发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到