解释如何发现循环开始节点的循环链表的工作？ [英] Explain how finding cycle start node in cycle linked list work?

问题描述

据我所知，乌龟和野兔的会议结束循环的存在，但如何移动龟链表开始，同时保持野兔在会场，其次是移动两个一步一步的时间让他们在出发点满足周期？

I understand that Tortoise and Hare's meeting concludes the existence of loop, but how does moving tortoise to beginning of linked list while keeping the hare at meeting place, followed by moving both one step at a time make them meet at starting point of cycle?

推荐答案

这是弗洛伊德的算法进行周期检测 。您问的是算法的第二阶段 - 一旦你找到了一个节点，这是一个循环的一部分，一个人如何找到的启动的周期

This is Floyd's algorithm for cycle detection. You are asking about the second phase of the algorithm -- once you've found a node that's part of a cycle, how does one find the start of the cycle?

在弗洛伊德的算法的第一部分，野兔移动两步乌龟的每一步。如果乌龟和野兔遇见，有一个周期，并在会议点是循环的一部分，但不一定在周期的第一个节点。

In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.

当乌龟和兔子相遇，我们已经发现了最小的我（所采取的龟步数），使得X <子>我 = X <子> 2I 。让亩重新present的步数自X <子> 0 到达周期的开始，并让拉姆达重新present的周期的长度。然后我=亩+一*波长，和2i =亩+ b *的拉姆达，其中a和b是整数，表示多少次乌龟和野兔绕到周期。减去 从第二所述第一公式给出I =（BA）*波长，所以i是整数倍数 的拉姆达。 因此，X <子> 1 +亩 = X <子>亩 。 X <子>我再presents乌龟和兔子的交汇点。如果将乌龟回到起始节点X <子> 0 ，并让乌龟和兔子继续以同样的速度，之后亩额外的步骤乌龟将达到X <子>亩 ，和兔子将达到X <子> 1 +亩 = X <子>亩，所以第二次会议点表示周期的开始。

When the tortoise and hare meet, we have found the smallest i (the number of steps taken by the tortoise) such that X_i = X_2i. Let mu represent the number of steps to get from X₀ to the start of the cycle, and let lambda represent the length of the cycle. Then i = mu + a*lambda, and 2i = mu + b*lambda, where a and b are integers denoting how many times the tortoise and hare went around the cycle. Subtracting the first equation from the second gives i = (b-a)*lambda, so i is an integer multiple of lambda. Therefore, X_{i + mu} = X_mu. X_i represents the meeting point of the tortoise and hare. If you move the tortoise back to the starting node X₀, and let the tortoise and hare continue at the same speed, after mu additional steps the tortoise will have reached X_mu, and the hare will have reached X_{i + mu} = X_mu, so the second meeting point denotes the start of the cycle.

这篇关于解释如何发现循环开始节点的循环链表的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！