在链表检测周期的开始证明 [英] Proof of detecting the start of cycle in linked list

问题描述

从计算器里外的几个职位，我已经知道如何检测周期一个链表，一个周期的长度。我还发现，关于如何检测循环的开始的方法。

From several posts inside stackoverflow and outside, I have come to know how to detect cycles in a linked list, the length of a cycle. I also found the method on how to detect the start of the loop.

下面是步骤重新仅供参考。

Here are the steps again for reference.

探测循环：

有两个指针，被称为经典的龟兔赛跑。移动野兔2步骤和乌龟1。如果他们在某一点相遇，那么肯定是一个周期，明显的交汇点是周期里面。

Have two pointers, classically called hare and tortoise. Move hare by 2 steps and tortoise by 1. If they meet at some point, then there is surely a cycle and the meeting point is obviously inside the cycle.

河套查找长度：

保持镇静指针固定在交汇点，同时增加其他直到他们原来的样子了。增加一个计数器，当您去，并在满足计数器的值将是周期的长度。

Keep one pointer fixed at meeting point while increment the other until they are same again. Increment a counter as you go along and the counter value at meet will be the length of cycle.

查找周期的开始

取一指针开始列表，并保持其他的交汇点。现在，由一个增加两个的相遇点是循环的开始。我验证了使用某些情况下在纸上的方法，但我不明白为什么它应该工作。

Take one pointer to start of the list and keep the other at the meeting point. Now increment both by one and the meet point is the start of loop. I verified the method using some cases on paper, but I don't understand why it should work.

有人可以提供一个数学证明，为什么这种方法可行？

Can someone, provide a mathematical proof as to why this method works?

推荐答案

您可以让您的查找周期的开始证明简单，如果你不使用的交汇点。
让第二个指针开始而不是在交汇点，但 M 步骤提前先指针。 （这里的 M 是环路的长度。）

You can make your 'Find the start of cycle' proof simpler if you don't use meeting point.
Let second pointer start not at the 'meeting point', but M steps ahead of first pointer. (Where M is the length of the loop.)

这样，证明pretty的明显。当第一个指针达到循环的开始，第二个会完全 M 步骤前进：此外，在循环的开始。

This way, proof is pretty obvious. When the first pointer reaches start of the loop, second will be exactly M steps ahead: also at the start of the loop.

这篇关于在链表检测周期的开始证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！