当前位置:   article > 正文

[寻找环链表入口点] 快慢指针数学原理剖析_为什么链表环形入口可以用快慢指针找到

为什么链表环形入口可以用快慢指针找到

链表环路检测及环入口定位是一个非常经典的算法问题,它可在死锁检测等实际应用场景发挥重要作用。想必大家都知道这个问题应该使用快慢指针去求解,因为它具有最优的时间复杂度O(n)。但是大家可能对快慢指针的数学原理不是很清楚,为啥它能达到最优。详细读了这篇文章,大家必定豁然开朗,掌握快慢指针背后的数学原理。

 我们直接来看图。

环路检测及入口定位原理分析图

先讲一下链表环路检测的原理,相比环入口定位,原理比较简单。

起点设置两个快慢指针,同时开始往后跑,每跑一次必须检测快指针是否到达链表末尾(下一个节点值为null),如果到达链表末尾则证明该链表无环。如果该链表存在环,则快慢指针总有邂逅(相遇)的那一刻,由此每跑一次,除了检测快指针是否到达链表末尾,还需检测快慢指针所在节点是否相同,相同则代表两指针相遇了,即环存在。为什么环存在时快慢指针一定会相遇呢,想必不用过多解释了,举个简单生活中例子,两个人在足球场跑步,同一起点出发,跑的快的人一定会在某一时刻追上跑的慢的人(多跑一圈)。

现在来分析环入口定位的原理。

环入口定位的前提是先找到快慢指针相遇点,即上述所讲的链表环检测操作(注意存在一个限定条件,快指针的步长必须为2,慢指针步长必须为1)。当找到相遇点后,在起点处和相遇点处分别设置指针p1和p2,步长均为1,它们同时往后跑,当p1,p2相遇时,它们的相遇点便是环入口。

现在来一波数学推理,证明一下上述算法的正确性。

x为起点至环入口点的距离,y为环入口至快慢指针相遇点的距离,z为快慢指针相遇点至环入口的距离。

假设相遇时,快指针绕环跑了m圈,则快指针所跑路程为x+y+m*c;慢指针绕环跑了n圈,则慢指针所跑路程为x+y+n*c。因为快指针速度为慢指针两倍,则相遇时快指针所跑路程亦为慢指针两倍,即2(x+y+n*c) = x+y+m*c

等式推导如下:

2(x+y+n*c) = x+y+m*c

2x+2y+2n*c = x+y+m*c

x = (m-2n)*c-y

x=(m-2n-1)*c+c-y

z=c-y(由图得知)

x=(m-2n-1)*c+z

由推导结果可知,起点至环入口的距离x为环周长c的(m-2n-1)倍再加快慢指针相遇点至环入口点的距离z。

在起点处和快慢指针相遇点处分别设置指针p1,p2,两指针速度一致,当p1走了(m2n1)c的距离时,p1所处位置距离环入口点的距离为z。此时,p2同样走了跟p1一样的距离(m2n1)c,即绕着环走了(m-2n-1)圈。

我们知道p2的出发点正好是快慢指针的相遇点,即便绕着环走了(m-2n-1)圈后,p2所处位置还是在快慢指针相遇点。因此,p2和环入口点的距离为z。

从上述推算,我们已经得知p1和p2距离环入口点的距离相同,均为z。

两个指针再往后走z的距离,便会相遇,相遇点便恰好是环入口点。

至此,环入口定位的算法原理讲解完毕。

现在来分析一波边界情况,以此证明上述公司的正确性。慢指针最少需要跑0圈,即进入环后第一次经过相遇点就被快指针追上了,所以n最小值为0。快指针要追上慢指针,至少要比慢指针多跑一圈,根据这些已知条件,可作推理如下:

已知 n>=0

已知 m>n

得 m>0,即m>=1

m=1,n=0 带入等式 x=(m-2n-1)*c+z

x>=0*c+z,即x>=z

因此,证明出x不可能为负,即起点距离环入口点距离不为负,符合常规事实,算法严谨性得证。

希望看完这篇文章的读者朋友们能够恍然大悟,掌握链表环问题的核心原理。如有不懂的地方,欢迎评论区留言。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/895232
推荐阅读
相关标签
  

闽ICP备14008679号