解释循环链表中查找循环开始节点的工作原理？

Question

我知道Tortoise和Hare的会议总结了循环的存在,但是如何将兔子移动到链接列表的开头同时将野兔保持在会场,然后一步一步地移动两个步骤使它们在循环的起始点相遇？

Answer 1

让我试着用我自己的话来澄清http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare提供的循环检测算法.

我参考这个数字 在我的解释中.

这个怎么运作

让我们有一只乌龟和一只野兔(指针的名字)指向一个循环的列表的开头.

让我们假设,如果我们一步一步地移动一步,一次只有两步,它们最终会在某一点上相遇.让我们说明首先这个假设是正确的.

该图说明了一个带循环的列表.循环的长度为n,我们最初m离开循环.还可以说,会议点k距离周期开始有一步之遥,乌龟和野兔在完成整个i步骤之后会相遇.

必须满足以下两个条件:

1) i = m + p * n + k

2) 2i = m + q * n + k

第一个说乌龟移动2i步骤,在这些i步骤中它首先进入循环.然后它会经历i一些正数的循环时间p.最后,它会越过p更多的节点,直到遇到野兔.

野兔也是如此.它会移动k步骤,在这些2i步骤中它首先进入循环.然后它会经历2i一些正数的循环时间q.最后,它会越过q更多的节点,直到遇到龟.

由于野兔的行进速度是乌龟的两倍,当它们到达会合点时,两者的时间都是恒定的.

因此,通过使用简单的速度,时间和距离关系,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

在m,n,k,p,q中,前两个是给定列表的属性.如果我们可以证明k,q,p至少有一组值使这个方程成立,那么我们就证明假设是正确的.

一个这样的解决方案集如下:

p = 0

q = m

k = m n - m

我们可以验证这些值的工作原理如下:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

对于这个集合,k是

i = m + p n + k

=> m + 0 * n + mn - m = mn.

当然,你应该看到这不一定是我可能的最小.换句话说,乌龟和兔子可能已经多次见过面了.然而,由于我们表明它们至少在某个时刻相遇,我们可以说假设是正确的.因此,如果我们将其中一个移动一步,而另一个移动一步两步,则必须满足.

现在我们可以进入算法的第二部分,即如何找到循环的开始.

循环开始

一旦乌龟和野兔见面,让我们把乌龟放回到清单的开头,并将野兔放在他们遇到的地方(距离循环开始的k步).

假设是,如果我们让它们以相同的速度移动(两者都是1步),它们第一次再次相遇将是循环的开始.

让我们来证明这个假设.

让我们首先假设一些oracle告诉我们m是什么.

然后,如果我们让它们移动m + k步,那么乌龟必须到达它们最初遇到的点(距离循环开始k步 - 见图).

以前我们证明了这一点i.

由于m + k步长是周期长度n的倍数,因此,平均时间内的野兔将经历周期(q-2p)次并且将返回到相同点(距离周期开始k步).

现在,不是让他们移动m + k步,如果我们让他们只移动m步,乌龟就会到达循环开始.野兔将完成(q-2p)轮换.由于它在循环开始前开始了k步,因此野兔必须在循环开始时到达.

结果,这解释了他们必须在第一次经过一些步骤后才开始在周期开始见面(这是第一次因为陆龟在m步之后到达周期而且它永远不会看到已经存在的野兔周期).

现在我们知道我们需要移动它们直到它们相遇的步数变成从列表开头到循环开始的距离,m.当然,算法不需要知道m是什么.它会一次一步地移动乌龟和野兔,直到它们相遇.会合点必须是循环开始,步数必须是循环开始的距离(m).假设我们知道列表的长度,我们还可以计算从列表长度中减去m的周期的长度.

Answer 2

参考此图片:

在meeting = x + y 之前slowPointer行进的距离

fastPointer在会议之前行进的距离 =(x + y + z)+ y = x + 2y + z

由于fastPointer行驶过程中双 slowPointer的速度,时间是恒定的,当到达会合点两种.

所以通过使用简单的速度,时间和距离关系2(x + y)= x + 2y + z => x + 2y + z = 2x + 2y => x = z

因此,通过将slowPointer移动到链接列表的开始,并使slowPointer和fastPointer一次移动一个节点,它们都具有相同的距离.

它们将在链接列表中的循环开始点到达.

Answer 3

这是Floyd的循环检测算法.您在询问算法的第二阶段 - 一旦您找到了一个循环的节点,如何找到循环的开始？

在弗洛伊德算法的第一部分中,野兔为乌龟的每一步移动两步.如果乌龟和野兔相遇,则存在一个循环,并且会合点是循环的一部分,但不一定是循环中的第一个节点.

当乌龟和野兔相遇时,我们发现了最小的i(乌龟所采取的步数),使得X _i = X _2i.令mu表示从X ₀到循环开始的步数,让lambda表示循环的长度.然后i = mu + a lambda,2i = mu + b lambda,其中a和b是整数,表示乌龟和野兔绕循环的次数.从第二个方程中减去第一个方程得到i =(ba)*lambda,因此i是lambda的整数倍. 因此,X _{i + mu} = X _mu.X _i代表乌龟和野兔的交汇点.如果将乌龟移回起始节点X.₀,让乌龟和野兔以相同的速度继续,经过额外的步骤,乌龟将达到X _亩,野兔将达到X _{i + mu} = X _mu,所以第二个会合点表示开始周期.

Answer 4

_{Old Monk的简单和低调的答案解释了当快速跑步者仅完成单个完整周期时找到周期.在这个答案中,我解释了当慢速跑步者进入循环之前快速跑步者多次运行循环的情况.}

使用相同的图像:

比方说,跑得最快的人已经跑环米之前慢速和快速满足倍.这意味着:

• 距离慢:x + y
• 通过快速运行的距离:x + m(y + z)+ y即它们相遇的额外y

由于快速运行的速度是慢速的两倍,并且它们已经运行了相同的时间,这意味着如果我们将距离增加一倍,我们就会快速地运行距离.从而,

• 2(x + y)= x + m(y + z)+ y

解决x给出,

x =(m-1)(y + z)+ z

在实际场景中,它意味着,x = (m - 1)完整循环运行+额外距离z.

因此,如果我们将一个指针放在列表的开头并将另一个指针留在会合点上,那么以相同的速度移动它们将导致in循环指针完成m-1次循环运行然后满足另一个指针就在循环开始处.

Answer 5

方法：

有两个指针：

• 一次移动一个节点的慢指针。
• 一次移动两个节点的快速指针。

如果两个指针相遇，则证明存在循环。一旦它们相遇，其中一个节点将指向头部，然后同时进行一个节点。他们将在循环开始时相遇。

理由： 当两个人沿着圆形轨道走时，其中一个人的速度是另一个人的两倍，他们在哪里相遇？正是他们开始的地方。

现在，假设快跑者k在n一步圈中领先一步。他们会在哪里见面？正是在n-k步骤。当慢跑者跑完(n-k)台阶时，快跑者会跑完k+2(n-k)台阶。（即k+2n-2k步骤即2n-k步骤）。即(n-k)步骤（路径是圆形的，我们不关心他们相遇的回合数；我们只关心他们相遇的位置）。

那么，快跑者最初是如何领先k一步的呢？因为慢跑者花了很多步才到达循环的起点。所以循环的开始是从头节点开始的 k 步。

注意：两个指针相遇的节点k离循环起点（循环内部）k一步之遥，头节点也离循环起点一步之遥。因此，当我们让指针从 bot 这些节点以 1 步的相同速度前进时，它们将在循环开始时相遇。

我相信这很简单。如果任何部分有歧义，请告诉我。

Answer 6

在第一次碰撞时,如上所示,乌龟移动了m + k步.野兔的移动速度是龟的两倍,这意味着兔子移动了2(m + k)步.从这些简单的事实我们可以得出以下图表.

在这一点上,我们将乌龟移回到起点并宣布兔子和乌龟必须一步一步地移动.根据定义,在m步之后,乌龟将处于循环的开始.兔子在哪里？

野兔也将在周期的开始.这是从第二张图明确:当乌龟被移回开始,兔子是ķ步入了最后一个周期.后米的步骤,野兔将完成一个循环,并与龟相撞.

Answer 7

好的，让我们假设兔子和乌龟在距离循环开始 k 步的点相遇，循环开始前的步数为 mu，循环的长度为 L。

所以现在在集合点 ->

乌龟覆盖的距离 = mu + a*L + k - 公式 1

（到达循环开始所采取的步骤 + 覆盖循环的“a”次迭代所采取的步骤 + 从循环开始的 k 步）（其中 a 是某个正常数）

野兔走过的距离 = mu + b*L + k - 公式 2

（到达循环开始所采取的步骤 + 覆盖循环的“b”次迭代所采取的步骤 + 从循环开始的 k 步）（其中 b 是某个正常数且 b>=a）

所以兔子所覆盖的额外距离是 = 方程 2 - 方程 1 = (ba)*L

请注意，这个距离也等于乌龟到起点的距离，因为兔子的移动速度是乌龟的 2 倍。如果我们不包括循环的多次遍历，这可以等同于“mu+k”，这也是会合点与起点的距离。

因此，mu + k = (ba)*L

因此，从这一点开始的 mu 步将导致回到循环的开始（因为从循环开始的 k 步已经被用于到达会合点）。这可能发生在同一周期或任何后续周期中。因此，现在如果我们将乌龟移动到链表的开头，需要 mu 步才能到达循环的起点，而兔子也需要 mu 步才能到达循环的开头，因此它们将在循环的起点。

PS 老实说，我脑子里和原来的海报有同样的问题，我读了第一个答案，他们确实清除了一些东西，但我无法清楚地得到最终结果，所以我尝试以自己的方式去做，发现它更容易理解。

Answer 8

非常非常简单。您可以考虑相对速度。如果兔子移动了两个节点，而乌龟移动了一个节点，则相对于乌龟兔子移动了一个节点（假设乌龟处于静止状态）。因此，如果我们在循环链接列表中移动一个节点，那么我们肯定会在那时再次碰面。

在圆形链表中找到连接点后，现在问题简化为找到两个链表问题的交点。

Answer 9

使用高中教授的相对速度的概念进行简单的解释- 物理 101/运动学讲座。

1. 假设从链表起点到圆起点的距离是x跳数。我们将圆的起点称为点X（大写字母 - 参见上图）。另外，我们假设圆的总大小为 N 跳。

2. 兔子的速度=2*乌龟的速度。所以分别是1 hops/sec和2 hops/sec

3. 当乌龟到达圆圈的起点时X，兔子必须进一步x跳到Y图中的点。（因为兔子跑的距离是乌龟的两倍）。

4. 因此，从 X 到 Y 顺时针旋转的剩余弧的长度将为N-x。这也恰好是兔子和乌龟能够相遇所需经过的相对距离。假设这个相对距离将被及时覆盖，即t_m见面的时间。相对速度为(2 hops/sec - 1 hops/sec)ie 1 hops/sec。因此，使用相对距离 = 相对速度 X 时间，我们得到t=N-x秒。N-x因此，乌龟和兔子都需要到达交汇点。

5. 现在，在N-x秒的时间和1 hops/sec速度下，较早到达该点的乌龟X将经过 Nx 跳到达集合点M。因此，这意味着交汇点M位于N-x从X= （这进一步暗示）=>到顺时针x方向剩余距离的逆时针跳跃处。MX

6. 但也是从链表起点x到达点的距离。X

7. 现在，我们不关心x对应的跳数是多少。如果我们将一只乌龟放在 LinkedList 的开头，将一只乌龟放在交汇点M，让它们跳跃/行走，那么它们将在点 处相遇X，这就是我们需要的点（或节点）。