| 【随想录6 | 您所在的位置：网站首页 › 什么叫二次相遇 › 【随想录6 |
【随想录6
|
试着解决如下问题
如何证明环形链表有环？为什么双指针一定会在环内相遇？如果快指针一次走三步是否一定相遇？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部分的验证代码 【随想录6 】环形链表与回文链表总结(带正确性证明) 如何找到入环节点代码随想录解释 证明一下上面方法的正确性代码随想录解释 翻译翻译： ------------------- | ^ 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 |
翻译翻译：
【本文地址】