试着解决如下问题
总结在最后
- 如何证明环形链表有环?
- 为什么双指针一定会在环内相遇?
- 如果快指针一次走三步是否一定相遇?5步呢?n步呢?
- 证明一下上一条
- 为什么此题快慢指针中,快指针比慢指针仅多走一步?为什么这么设置?
- 如何找到入环节点
- 证明一下上面方法的正确性
如何证明环形链表有环?
leetcode 141 题自己搜
为什么双指针一定会在环内相遇?
来自代码随想录群友 穿靴子的猫
的解释
假设快指针一次走x步,慢指针一次y步,相遇意味着二者路程差了n圈,一圈长度是C,则经过t时间,xt-yt=nC,n是快指针比慢指针多走的圈数,只要保证t=nC/(x-y)有整数解即可,令n=x-y,则必会相遇
为什么此题快慢指针中,快指针比慢指针仅多走一步?为什么这么设置?
源地址:https://stackoverflow.com/a/23662769
翻译翻译:
让我们假设不包含循环的列表的长度 be s,循环的长度 bet和fast_pointer_speed to slow_pointer_speed 的比率k。
(不包含环的节点长度为 s,环长度为t ,快慢指针速度比率为 k )
让两个指针在距 j 循环起点一定距离处相遇。
因此,慢速指针移动的距离 = s + j。快速指针移动的距离 = s + j + m * t(其中m是快速指针完成循环的次数)。但是,快速指针也会移动一段距离 k * (s + j) (k为速度比率)。
因此,我们得到k * (s + j) = s + j + m * t。
s + j = (m / k-1)t.
因此,根据上面的等式,慢指针移动的长度是循环长度的整数倍。
为了获得最大的效率,(m / k-1) = 1(慢指针不应多次遍历循环。)
所以 , m = k - 1 => k = m + 1
由于m是快速指针完成循环的次数,m >= 1。为了获得最大的效率,m = 1。
因此k = 2。
如果我们取值为k > 2,则两个指针必须移动的距离越大。
希望以上解释有帮助。
如果快指针一次走三步是否一定相遇?5步呢?n步呢?
简单证明一下上一条
可以看下本博客的第2个问题
假设快指针一次走x步,慢指针一次y步,相遇意味着二者路程差了n圈,一圈长度是C,则经过t时间,xt-yt=nC,n是的圈数,只要保证t=nC/(x-y)有整数解即可,令n=x-y,则必会相遇
这里涵盖了所有可能性,无论快慢指针速度比是多少,只要他俩都是整数速度,就一定能相遇
还可以看这个博客的第2部分的验证代码
如何找到入环节点
证明一下上面方法的正确性
翻译翻译:
-------------------
| ^
v |
0->1->2->3-> …… -> A ->....... -> B
假设A为环入口,B为相遇点,设0到A距离为x,
A到B距离为y,环的长度为c,
快慢指针相遇是慢指针绕环n圈,快指针绕环m圈,
由条件得快慢指针相遇时快指针走的长度是慢指针的2倍,则:
2(x+nc+y)=x+mc+y;
化简得x+y=(m-2n)c;
这意味着从起点0相遇点B的长度为环长度的正整数倍;
换句话说,就是现在让两个指针速度都变成1(重点!!!),
第一个指针从起点0出发,第二个指针从相遇点B出发,
则两个指针最后一定会在B点相遇;
但这是两个指针第一次相遇吗?
不,因为两个指针速度是相同的,
所以往前退一退,就会发现两个指针其实是在环的入口第一次相遇后,就一直重合了;
所以代码就转换成两个速度为1的指针,一个从起点出发,一个从B点出发,第一次相遇的节点即为入环点。
源链接:https://stackoverflow.com/a/36214925
总结
-
链表内存在环时,只要快慢指针同时从起点走,速度比为 n :1 ,都可以找到环,且在环中相遇。
-
相遇后,快指针回到head,和慢指针一起走,相等时即为环入口。
通过模型化可以得出:
从头节点到相遇点的长度为环长度的正整数倍
也就是说
此时,从头节点与相遇点同时开始向后移动,一定会在环入口相遇。 -
指针移动的步数与环的大小有关,与速度比没有关系
但当速度比为1:2时,快指针移动步数最小,即总体算法时间复杂度最小