解释在循环链表中查找循环起始节点是如何工作的? [英] 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?

在 Floyd 算法的第一部分中，兔子每走一步就移动两步.如果乌龟和兔子相遇，则存在一个循环，并且相遇点是循环的一部分，但不一定是循环中的第一个节点.

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.

当乌龟和兔子相遇时，我们已经找到了最小的 i(乌龟走的步数)，使得 X_i = X_2i.让 mu 表示从 X₀ 到循环开始的步数，让 lambda 表示循环的长度.然后 i = mu + alambda，和 2i = mu + blambda，其中 a 和 b 是整数，表示乌龟和兔子在循环中走了多少次.减法第二个方程的第一个方程给出 i = (b-a)*lambda，所以 i 是整数倍拉姆达的.因此，X_{i + mu} = X_mu.X_i 代表龟兔的交汇点.如果你把乌龟移回起始节点X₀，让乌龟和兔子以相同的速度继续前进，经过mu额外的步骤后乌龟将到达X_mu，兔子将达到 X_{i + mu} = X_mu，所以第二个交汇点表示循环的开始.

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 + alambda, and 2i = mu + blambda, 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屋！