我们怎样才能找到链接列表循环的起始节点？ [英] How can we find the starting node of a loop in link list?

问题描述

按照弗洛伊德的圈发现算法中，乌龟和野兔满足点解释了循环性质的链接列表。

要发现在周期起始节点我们初始化龟指针到列表的头部，并开始由一个单位递增龟兔赛跑指针。在那里他们满足点表示周期的开始节点

请告诉我它是如何工作的特定情况。

链接列表流向为：

  1→2→3→4- GT; 5→6＆GT; 7＆GT; 8＆GT; 3
 

解决方案

让我们来看看。

您快两倍定位兔子和乌龟1，并让他们跑，兔子的乌龟。

目前第零步骤，都是在1在第一步骤，乌龟移动到2和野兔移动到3，依此类推。

  1 1
2 3
3 5
4 7
5 3
6 5
7 7
 

于是，兔子和7乌龟相遇。

现在将乌龟之初，并让他们以相同的速度再次运行，现在。

  1 7
2 8
3 3
 

因此​​，他们确实已经达到在周期的第一个元素。

这就是它是如何工作的对于给定的情况下的。

According to the Floyd's cycle finding algorithm, the point where tortoise and hare meets explains the circular nature in the link list.

To find the starting node in the cycle we initialize tortoise pointer to head of the list and starts incrementing hare and tortoise pointer by one unit. The point where they meet denotes the starting node of the cycle.

Please tell me how it works for the given situation.

The link list flows as:

1->2->3->4->5->6->7->8->3

解决方案

Let's see.

You position the hare and the tortoise at 1, and let them run, the hare twice as fast as the tortoise.

At the zeroth step, both are at 1. At the first step, the tortoise moves to 2 and the hare moves to 3, and so on.

1 1
2 3
3 5
4 7
5 3
6 5
7 7 

So the hare and the tortoise meet at 7.

Now place the tortoise at the beginning, and let them run again, now with the same speed.

1 7
2 8
3 3 

So they indeed have met at the first element of the cycle.

And that's how it works for the given situation.

这篇关于我们怎样才能找到链接列表循环的起始节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！