如何在循环链表中找到循环起始节点？

时光无声 2024-09-10 14:37:24

在花了两个小时尝试阅读所有答案后，我在 leetcode 上发现了这条评论。可以肯定地说，它拯救了我的夜晚。

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation./44281

< a href="https://i.sstatic.net/4fgWa.png" rel="nofollow noreferrer"> 输入图像描述这里

回复收藏 0 原文

┈┾☆殇 2024-09-10 14:37:24

我看到大多数答案都给出了数学解释“如何将乌龟移动到链表的开头，同时将兔子保持在相遇位置，然后一次移动一步使它们在循环的起点相遇？”

下面的方法也在幕后执行与 floyd 循环检测相同的操作，但原理很简单，但代价是 O(n) 内存。

我想添加一个更简单的方法/理由来找到周期的开始。由于这个方法没有在任何地方提到，我在这里测试了这个： https://leetcode.com/problems/linked-list-cycle-ii/< /a> 并且它通过了所有测试用例。

让我们考虑一下我们已经获得了 LinkedList 的头引用。

     public ListNode detectCycle(ListNode head) {
     
            // Consider a fast pointer which hops two nodes at once.
            // Consider a slow pointer which hops one node at once.
            // If the linked list contains a cycle,
            // these two pointers would meet at some point when they are looping around the list.
            // Caution: This point of intersection need not be the beginning of the cycle.
            ListNode fast = null;
            ListNode slow = null;
            if (head != null) {
                if (head.next != null) {
                    fast = head.next.next;
                    slow = head;
                } else {
                    return null;
                }
            }
            while (fast != null && fast.next != null) {
                // Why do we need collection here? Explained below
                Set<ListNode> collection = new HashSet<>();
                if (fast == slow) {
                  // Once the cycle is detected, 
                     we are sure that there is beginning to the cycle.
                  // In order to find this beginning, 
                  // 1. move slow pointer to head and keep fast pointer at 
                        the meeting point.
                  // 2. now while moving slow and fast pointers through a 
                        single hop, store the slow reference in a collection.
                  // 3. Every time you hop the fast pointer, check the fast 
                        pointer reference exits in that collection.
                  // Rationale: After we moved slow pointer to the head, 
                     we know that slow pointer is coming behind the fast
                     pointer, since collection is storing all nodes from the 
                     start using slow pointer, there is only one case we get 
                     that fast pointer exists in the collection when slow 
                     pointer started storing the nodes which are part of the 
                     cycle. Because slow pointer can never go ahead of fast 
                     pointer since fast pointer already has an head-start, at 
                     the same time, the first occurence will always be of the 
                     starting point of the cycle because slow pointer can't 
                     go ahead of fast pointer to store other nodes in the 
                     cycle. So, the moment we first find fast pointer in that 
                     collection means, that is the starting point of the 
                     cycle.
                    slow = head;
                    collection.add(slow);
                    while (!collection.contains(fast)) {
                        slow = slow.next;
                        collection.add(slow);
                        fast = fast.next;
                    }
                    return fast;
                }
                fast = fast.next.next;
                slow = slow.next;
            }
            return null;
        }

I see that most of the answers giving mathematical explanation for this "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?"

The following method also does the same like floyd cycle detection behind the scenes but the rationale is simple but at a cost of O(n) memory.

I would like to add an easier approach/rationale to find the beginning of the cycle. Since this method was not mentioned anywhere, I tested this here: https://leetcode.com/problems/linked-list-cycle-ii/ and It passed all the testcases.

Let's consider that we've been given head reference of the LinkedList.

     public ListNode detectCycle(ListNode head) {
     
            // Consider a fast pointer which hops two nodes at once.
            // Consider a slow pointer which hops one node at once.
            // If the linked list contains a cycle,
            // these two pointers would meet at some point when they are looping around the list.
            // Caution: This point of intersection need not be the beginning of the cycle.
            ListNode fast = null;
            ListNode slow = null;
            if (head != null) {
                if (head.next != null) {
                    fast = head.next.next;
                    slow = head;
                } else {
                    return null;
                }
            }
            while (fast != null && fast.next != null) {
                // Why do we need collection here? Explained below
                Set<ListNode> collection = new HashSet<>();
                if (fast == slow) {
                  // Once the cycle is detected, 
                     we are sure that there is beginning to the cycle.
                  // In order to find this beginning, 
                  // 1. move slow pointer to head and keep fast pointer at 
                        the meeting point.
                  // 2. now while moving slow and fast pointers through a 
                        single hop, store the slow reference in a collection.
                  // 3. Every time you hop the fast pointer, check the fast 
                        pointer reference exits in that collection.
                  // Rationale: After we moved slow pointer to the head, 
                     we know that slow pointer is coming behind the fast
                     pointer, since collection is storing all nodes from the 
                     start using slow pointer, there is only one case we get 
                     that fast pointer exists in the collection when slow 
                     pointer started storing the nodes which are part of the 
                     cycle. Because slow pointer can never go ahead of fast 
                     pointer since fast pointer already has an head-start, at 
                     the same time, the first occurence will always be of the 
                     starting point of the cycle because slow pointer can't 
                     go ahead of fast pointer to store other nodes in the 
                     cycle. So, the moment we first find fast pointer in that 
                     collection means, that is the starting point of the 
                     cycle.
                    slow = head;
                    collection.add(slow);
                    while (!collection.contains(fast)) {
                        slow = slow.next;
                        collection.add(slow);
                        fast = fast.next;
                    }
                    return fast;
                }
                fast = fast.next.next;
                slow = slow.next;
            }
            return null;
        }

回复收藏 0 原文

蓝颜夕 2024-09-10 14:37:24

我知道这个问题已经有一个公认的答案，但我仍然会尝试以流畅的方式回答。
假设：

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

现在，让兔子和乌龟从一开始就在时间“t”之后相遇。

观察：

如果，乌龟行驶的距离 = v*t = x + (bk) （比如说）

那么，野兔行驶的距离 = 2*v*t = x + (b - k) + b （因为野兔有已经遍历了循环部分一次）

现在，会议时间是相同的。

=> x + 2*b - k = 2* (x + b - k)

=> x = k

这当然意味着不循环的路径长度与循环起点到两者相遇点的距离相同。

I know there is already an accepted answer for this problem but I'll still try to answer in a fluid manner.
Assume :

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

Now, let the hare and the tortoise meet after time 't' from beginning.

Observations:

If, Distance traveled by the tortoise = v*t = x + (b-k) (say)

Then, Distance traveled by the hare = 2*v*t = x + (b - k) + b (since the hare has traversed the looped part once already)

Now, there meeting times are same.

=> x + 2*b - k = 2* (x + b - k)

=> x = k

This of course means that the length of the path that is not looped is same as the distance of the starting point of the loop from the point where both meet.

回复收藏 0 原文

得不到的就毁灭 2024-09-10 14:37:24

假设您的指针在 y 点和 z 点的交点处相交。

n 和 m 分别是更快和更慢的指针在相遇之前所经过的循环次数。

请参阅图片以获取证明的其余部分。
查找链表循环起点

回复收藏 0 原文

百合的盛世恋 2024-09-10 14:37:23

让我尝试以我自己的方式阐明 Wikipedia - Tortoise_and_hare 中提供的周期检测算法字。

drawing

工作原理

让我们有一只乌龟和一只兔子（指针的名称）指向列表的开头有一个循环，如上图所示。

我们假设，如果乌龟每次移动 1 步，兔子每次移动 2 步，它们最终会在一点相遇。首先让我们证明这个假设是正确的。

该图展示了一个带有循环的列表。循环的长度为 n，我们最初距离循环还有 m 步。另外，假设交汇点距离循环起点有 k 步，当乌龟总共走了 i 步时，乌龟和兔子相遇。（到那时，野兔总共已走了 2i 步。）。

必须满足以下两个条件：

1) i = m + p * n + k

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

第一个条件表示乌龟移动了 i 步，并且在这 i 步中，它首先进入循环。然后它会针对某个正数 p 循环 p 次。最后，它又经过k 个节点，直到遇到兔子。

野兔也有类似的情况。它移动 2i 步，并在这些 2i 步中首先进入循环。然后它会针对某个正数 q 循环 q 次。最后，它又经过 k 个节点，直到遇到乌龟。

由于兔子的行进速度是乌龟的两倍，所以当它们到达交汇点时，时间是恒定的。

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

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

对于这个集合，i 是

i = m + p n + k

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

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

现在我们可以进入算法的第二部分，即如何找到循环的起点。

循环开始

一旦乌龟和兔子相遇，让我们将乌龟放回列表的开头，并将兔子保留在它们相遇的位置（距循环开始k步）。

假设是，如果我们让它们以相同的速度移动（两者均为 1 步），那么它们第一次再次相遇将是循环的开始。

让我们来证明这个假设。

我们首先假设某个预言告诉我们m 是什么。

然后，如果我们让它们移动 m + k 步，乌龟必须到达它们最初相遇的点（距循环起点 k 步 - 请参阅数字）。

之前我们展示了m + k = (q - 2p) n。

由于 m + k 步数是循环长度 n 的倍数，因此兔子同时会经历该循环 (q-2p)次，并且会回到同一点（距循环起点 k 步）。

现在，如果我们让它们只移动 m 步，而不是让它们移动 m + k 步，那么乌龟就会到达循环开始处。 Hare 距离完成 (q-2p) 旋转还差 k 步。由于它在循环开始之前启动了 k 步，因此兔子必须到达循环开始处。

因此，这解释了它们必须在第一次走了一定步数后在循环开始时相遇（第一次是因为乌龟在 m 步后才到达循环，并且它永远看不到已经在循环中的兔子）。

现在我们知道，我们需要移动它们直到它们相遇的步数是从列表开头到循环开头的距离，m。当然，算法不需要知道m是什么。它只会让乌龟和兔子一步一步地移动，直到它们相遇。交汇点必须是循环起点，步数必须是到循环起点的距离 (m)。假设我们知道列表的长度，我们还可以计算从列表长度中减去m的循环长度。

Let me try to clarify the cycle detection algorithm that is provided at Wikipedia - Tortoise_and_hare in my own words.

drawing

How it works

Let's have a tortoise and a hare (name of the pointers) pointing to the beginning of the list with a cycle, as in the diagram above.

Let's hypothesize that if we move the tortoise 1 step at a time, and the hare 2 steps at a time, they will eventually meet at a point. Let's show that first of all this hypothesis is true.

The figure illustrates a list with a cycle. The cycle has a length of n and we are initially m steps away from the cycle. Also, let's say that the meeting point is k steps away from the cycle beginning and tortoise and hare meets when tortoise has taken i total steps. (Hare would have taken 2i total steps by then.).

The following 2 conditions must hold:

1) i = m + p * n + k

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

The first one says that the tortoise moves i steps and in these i steps, it first gets to the cycle. Then it goes through the cycle p times for some positive number p. Finally, it goes over k more nodes until it meets hare.

A similar thing is true for hare. It moves 2i steps and in these 2i steps it first gets to the cycle. Then it goes through the cycle q times for some positive number q. Finally, it goes over k more nodes until it meets the tortoise.

As the hare travels with double the speed of the tortoise, and time is constant for both when they reach the meeting point.

So by using simple speed, time and distance relation,

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

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

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

Among m, n, k, p, q, the first two are properties of the given list. If we can show that there is at least one set of values for k, q, p that makes this equation true we show that the hypothesis is correct.

One such solution set is as follows:

p = 0

q = m

k = m n - m

We can verify that these values work as follows:

m + k = ( q - 2p ) n  

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

=> mn = mn

For this set, i is

i = m + p n + k

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

Of course, you should see that this is not necessarily the smallest i possible. In other words, tortoise and hare might have already met before many times. However, since we show that they meet at some point at least once we can say that the hypothesis is correct. So they would have to meet if we move one of them by 1 step, and the other one by 2 steps at a time.

Now we can go to the second part of the algorithm which is how to find the beginning of the cycle.

Cycle Beginning

Once tortoise and hare meet, let's put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning).

The hypothesis is that if we let them move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.

Let's prove this hypothesis.

Let's first assume some oracle tells us what m is.

Then, if we let them move m + k steps, the tortoise would have to arrive at the point they met originally (k steps away from the cycle beginning - see in the figure).

Previously we showed that m + k = (q - 2p) n.

Since m + k steps is a multiple of cycle length n, hare, in the meantime, would go through the cycle (q-2p) times and would come back to the same point (k steps away from the cycle beginning).

Now, instead of letting them move m + k steps, if we let them move only m steps, the tortoise would arrive at the cycle beginning. Hare would be k steps short of completing (q-2p) rotations. Since it started k steps in front of the cycle beginning, the hare would have to arrive at the cycle beginning.

As a result, this explains that they would have to meet at the cycle beginning after some number of steps for the very first time (very first time because the tortoise just arrived at the cycle after m steps and it could never see hare which was already in the cycle).

Now we know that the number of steps we need to move them until they meet turns out to be the distance from the beginning of the list to the cycle beginning, m. Of course, the algorithm does not need to know what m is. It will just move both tortoise and hare one step at a time until they meet. The meeting point has to be the cycle start and the number of steps must be the distance (m) to the cycle beginning. Assuming we know the length of the list, we can also, compute the length of the cycle of subtracting m from the list length.

回复收藏 0 原文

故事灯 2024-09-10 14:37:23

请参考此图片：

slowPointer 在会面之前行驶的距离 = x + y

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 一次移动一个节点，它们都有相同的覆盖距离 。

它们将到达链表中循环开始的点。

回复收藏 0 原文

空城旧梦 2024-09-10 14:37:23

这是Floyd 自行车检测算法。您问的是算法的第二阶段 - 一旦找到属于循环一部分的节点，如何找到循环的开始？

在弗洛伊德算法的第一部分中，乌龟每走一步，兔子就移动两步。如果乌龟和兔子曾经相遇，那么就有一个循环，并且相遇点是循环的一部分，但不一定是循环中的第一个节点。

当乌龟和兔子相遇时，我们找到了最小的i（乌龟走了的步数），使得X_i = X_2i。让 mu 代表从 X₀ 到循环开始的步数，让 lambda 代表循环的长度。那么 i = mu + alambda，2i = mu + blambda，其中 a 和 b 是整数，表示乌龟和兔子绕了一圈的次数。减法
第二个方程中的第一个方程给出 i = (ba)*lambda，因此 i 是整数倍
拉姆达。 因此，X_{i + mu} = X_mu。 X_i 代表乌龟和兔子的交汇点。如果将乌龟移回起始节点 X₀，并让乌龟和兔子以相同的速度继续前进，那么再经过 mu 步，乌龟将到达 X_mu ，并且野兔将达到 X_{i + mu} = X_mu，因此第二个交汇点表示循环的开始。

回复收藏 0 原文

无言温柔 2024-09-10 14:37:23

_{老和尚的简单且未被投票的答案解释了当快速跑步者仅完成一次完整时找到循环循环。在这个答案中，我解释了快速运行者在慢速运行者进入循环之前多次运行循环的情况。}

使用相同的图像：

假设跑得快的人有在慢速和快速相遇之前运行循环 m 次。这意味着：

慢跑距离：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。

因此，如果我们将一个指针放在列表的开头并将另一个指针留在交汇点，那么以相同的速度移动它们将导致循环指针完成 m - 1 次运行循环，然后在循环开始处遇到另一个指针。

回复收藏 0 原文

原谅我要高飞 2024-09-10 14:37:23

这非常非常简单。您可以从相对速度的角度来思考。如果兔子移动了两个节点，乌龟移动了一个节点，相对于乌龟来说，兔子移动了一个节点（假设乌龟静止）。因此，如果我们移动循环链表中的一个节点，我们肯定会再次在该点相遇。

找到循环链表内部的连接点后，现在问题就简化为找到两个链表的交点问题。

回复收藏 0 原文

夜空下最亮的亮点 2024-09-10 14:37:23

方法：

有两种指针：

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

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

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

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

那么，快跑者最初是如何领先 k 步的呢？因为慢跑者需要很多步才能到达循环的起点。所以循环的起点距离头节点 k 步。

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

我相信这很简单。如果有任何部分不明确，请告诉我。

回复收藏 0 原文

满意归宿 2024-09-10 14:37:23

图 1

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

此时，我们将乌龟移回起点，并声明兔子和乌龟都必须移动一步一次。根据定义，在 m 步之后，乌龟将处于循环的开始位置。野兔会在哪里？

野兔也将处于周期的开始。从第二张图中可以清楚地看出：当乌龟移回到起点时，兔子k步进入了最后一个循环。在m步之后，兔子将完成另一个循环并与乌龟相撞。

回复收藏 0 原文

薄荷港 2024-09-10 14:37:23

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

现在在交汇点->

乌龟走过的距离 = mu + a*L + k - 方程 1

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

野兔覆盖的距离 = mu + b*L + k - 方程 2

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

因此，兔子所走过的额外距离 = 方程 2 - 方程 1 = (ba)*L

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

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

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

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

回复收藏 0 原文

禾厶谷欠 2024-09-10 14:37:23

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

假设从链表起点到圆起点的距离是 x 跳。我们将圆的起点称为点 X（大写字母 - 参见上图）。另外，我们假设圆的总大小为 N 跳。
兔子的速度 = 2 * 乌龟的速度。因此，分别是 1 跳/秒 和 2 跳/秒
当乌龟到达圆的起点 X 时，兔子必须进一步在图中的点Y处x跳。（因为兔子跑的距离是乌龟的两倍）。
因此，从 X 到 Y 顺时针旋转的剩余弧的长度将为 Nx。这也恰好是兔子和乌龟能够相遇所需经过的相对距离。假设这个相对距离将在 t_m 时间内完成，即见面时间。相对速度为（2 跳/秒 - 1 跳/秒） 即1 跳/秒。因此，使用相对距离=相对速度X时间，我们得到t=Nx秒。因此，乌龟和兔子都需要 Nx 才能到达交汇点。
现在，在 Nx 秒的时间内，以 1 跳/秒 的速度，之前在 X 点的乌龟将跳 Nx 跳到到达集合点M。因此，这意味着汇合点 M 位于从 X 逆时针方向 Nx 跳处 =（这进一步暗示）=>从点 M 到 X 顺时针还有 x 距离。
但是x也是从链表起点到达点X的距离。
现在，我们不关心 x 对应的跳数是多少。如果我们将一只乌龟放在 LinkedList 的开头，将一只乌龟放在交汇点 M 并让它们跳跃/行走，那么它们将在点 X 交汇，即我们需要的点（或节点）。

回复收藏 0 原文

北音执念 2024-09-10 14:37:23

将问题简化为循环问题，然后回到最初的问题

我发现下面的解释更直观。

取两个从头部 (O) 开始的指针（1 = 乌龟和 2 = 兔子），1< /strong> 的步长为 1，2 的步长为 2。考虑一下 1 到达该循环的起始节点 (A) 的时刻。
我们想要回答以下问题“当 1 在 A 中时 2 在哪里？”。
因此，OA = a 是一个自然数 (a >= 0)。但可以写成：a = k*n + b，其中a、k、n、b是自然数：
n = 周期长度
k >= 0 = 常数
0 <= b <= n-1
这意味着b = a % n。
例如：如果a = 20且n = 8 => k = 2 和 b = 4 因为 20 = 2*8 + 4。
1 所覆盖的距离为 d = OA = a = k*n + b。但同时，2 涵盖了 D = 2*d = d + d = OA + d = OA + k*n + b。这意味着当 2 在 A 中时，它必须覆盖 k*n + b。正如你所看到的，k 是圈数，但是在这些圈之后，2 将距离 A 很远b。所以，我们发现其中 2 是当 1 在 A 中时。我们将该点称为 B，其中 AB = b。
现在，我们将问题简化为一个圆圈。问题是“集合点在哪里？”。那个C在哪里？
在每一步中，2 都会将与 1 的距离减小为 1（假设为米），因为 1距离 2 和 1 越来越远，但同时 2 距离 1 更接近 2.
因此，当 1 和 2 之间的距离为零时，即为交集。这意味着 2 减少了 n - b 距离。为了实现这一点，1 将执行 n - b 步，而 2 将执行 2*(n - b)< /code> 步骤。
因此，交点距离 A 的距离将是 n - b（顺时针），因为这是 1 所经过的距离，直到它满足2。 => C 和 A 之间的距离为 CA = b，因为 AC = AB + BC = n - b 且CA = n - AC。不要认为AC = CA，因为AC距离不是一个微不足道的数学距离，它是A和A之间的步数C（其中A是起点，C是终点）。
现在，让我们回到初始架构。
我们知道a = k*n + b和CA = b。
我们可以采用两个新指针1'和1''，其中1'从头部开始（O< /strong>) 和 1'' 从交点 (C) 开始。
1' 从 O 到 A，而 1'' 从 C< /strong> 到 A 并继续完成 k 圈。因此，交点是A。

Reduce the problem to a loop problem, then go back to the initial problem

I find the following explanation more intuitive.

Take two pointers (1 = tortoise and 2 = hare) that start from the head (O), 1 has a step length of 1, 2 has a step length of 2. Think about the moment when 1 reaches the start node of that cycle (A).
We want to answer to the following question "Where is 2 when 1 is in A?".
So, OA = a is a natural number (a >= 0). But it can be written in the following way: a = k*n + b, where a, k, n, b are natural numbers:
- n = the cycle length
- k >= 0 = constant
- 0 <= b <= n-1
It means that b = a % n.
E.g.: if a = 20 and n = 8 => k = 2 and b = 4 because 20 = 2*8 + 4.
The distance covered by 1 is d = OA = a = k*n + b. But in the same time, 2 covers D = 2*d = d + d = OA + d = OA + k*n + b. This means that when 2 is in A it has to cover k*n + b. As you can see, k is the number of laps, but after those laps, 2 will be b far from A. So, we found where 2 is when 1 is in A. Let's call that point B, where AB = b.
Now, we reduce the problem to a circle. The question is "Where is the meeting point?". Where is that C?
In every step, 2 reduces the distance from 1 with 1 (let's say meter) because 1 is getting further from 2 with 1, but at the same time 2 goes closer to 1 by 2.
So, the intersection will be when the distance between 1 and 2 will be zero. This means that 2 reduces the n - b distance. In order to achieve this, 1 will make n - b steps, while 2 will make 2*(n - b) steps.
So, the intersection point will be n - b far from A (clockwise), because this is the distance covered by 1 until it meets 2. => the distance between C and A is CA = b, because AC = AB + BC = n - b and CA = n - AC. Don't think that AC = CA, because the AC distance is not a trivial mathematical distance, it is the number of steps between A and C (where A is the start point and C is the end point).
Now, let's go back to the initial schema.
We know that a = k*n + b and CA = b.
We can take 2 new pointers 1' and 1'', where 1' starts from the head (O) and 1'' starts from the intersection point (C).
While 1' goes from O to A, 1'' goes from C to A and continues to finish k laps. So, the intersection point is A.

回复收藏 0 原文

雪化雨蝶 2024-09-10 14:37:23

如果如图所示，指针交汇于 P 点，则 Z+Y 的距离就是 P 点，X+Y 也是 P 点，即 Z=X。这就是为什么保持从 P 开始移动一个指针并从起点（S）移动另一个指针直到它们相遇，这意味着将相等的距离（Z 或 X）移动到同一点 M（距离 P 和 X 距离 S）将是循环的开始。简单的！

回复收藏 0 原文

幸福丶如此 2024-09-10 14:37:23

对此已经有很多答案，但我曾经为此想出了一个图表，这对我来说在视觉上更直观。也许它可以帮助其他人。

对我来说主要的顿悟时刻是：

将T（乌龟）分成T1（循环前）和T2（在-环形）。
从 H 中减去 T，它们在视觉上重叠。剩下的 (H - T = H') 等于 T。
剩下的数学很简单。

回复收藏 0 原文

花桑 2024-09-10 14:37:23

-循环之前有k步。我们不知道 k 是什么，也不需要找出来。我们可以只用 k 进行抽象工作。

--k 步之后

----- T 处于循环开始

----- H 是 k 步进入循环（他总共走了 2k 步，因此 k 进入循环）

** 它们现在是循环大小 - k 相距

（注意 k == K == mod(loopsize, k) --例如，如果一个节点以 2 步进入 5 节点循环，那么它也是 7、12 或 392 步，因此循环有多大 k 并不考虑在内

。它们以每单位时间 1 步的速度相互追赶，因为一个的移动速度是另一个的两倍，它们将以循环大小 - k 相遇，

这意味着需要 k 个节点才能到达循环的开始，并且因此，从头部到循环开始的距离和碰撞到循环开始的距离是相同的，

所以现在，如果您以 1 的速率移动，则将 T 移回头部 T 和 H 将在循环开始处相遇（两者均以 k 步移动）

。意味着算法是：

从头部移动 T = t.next 和 H.next.next 直到它们碰撞 ( T == H) （有一个循环）

//注意 k=0 或 T 和 H 相遇时的情况在循环的头部
计算循环长度

-- 通过用计数器在循环周围移动 T 或 H 来计算循环的长度

-- 将指针 T2 移至链表头部

-- 移动循环步骤的指针长度

-- 将另一个指针 H2 移至链表头部

--串联移动 T2 和 H2 直到它们在周期开始时相遇，

就是这样！

回复收藏 0 原文

乙白 2024-09-10 14:37:23

图片来源

调用 distance 表示指针所遵循的链接数，将 time 表示算法将慢速指针移动一个链接和将快速指针移动两个链接所需的迭代次数。在长度为 C 的循环之前有 N 个节点，标记为循环偏移 k=0 到 C-1。

要到达循环的起点，慢速需要 N 时间和距离。这意味着快速在循环中需要 N 距离（N 到达那里，N 旋转）。因此，在时间 N，慢速位于周期偏移 k=0，而快速位于周期偏移 k=N mod C。

如果 N mod C 为零，则慢速和快现在匹配，并且在时间 N 和周期位置 k 找到周期=0。

如果 N mod C 不为零，则快的现在必须赶上慢的，此时 N 是循环中落后的 C-(N mod C) 距离。

由于慢速每移动 1，快速移动 2，每次迭代时距离都会减少 1，因此这需要与时间 N 时快慢之间的距离一样多的额外时间，即 C-(N mod C)。由于 Slow 是从偏移量 0 开始移动，因此这也是它们相遇的偏移量。

因此，如果 N mod C 为零，则阶段 1 在循环开始时的 N 次迭代后停止。否则，阶段 1 在 N+C-(N mod C) 次迭代后以偏移量 C-(N mod C) 进入周期停止。

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

好的，所以阶段 2：慢速需要 N 个以上的步骤才能进入循环，此时快速（现在每个时间步移动 1）位于 (C-(N mod C)+N) mod C = 0。所以它们满足在第 2 阶段之后的循环开始时。

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

为了完整起见，第 3 阶段通过再次移动循环来计算循环长度：

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

image credit

Call distance the number of links a pointer follows, and time the number of iterations the algorithm takes of moving the slow pointer one link and the fast pointer two links. There are N nodes before a cycle of length C, labeled with cycle offset k=0 through C-1.

To reach the start of the cycle, slow takes N time and distance. This means fast takes N distance in the cycle (N to get there, N to spin). So at time N, slow is at cycle offset k=0, and fast is at cycle offset k=N mod C.

If N mod C is zero, slow and fast now match and the cycle is found at time N and cycle position k=0.

If N mod C is not zero, then fast now has to catch up with slow, which at time N is C-(N mod C) distance behind in the cycle.

Since fast moves 2 for every 1 of slow, reducing the distance by 1 on every iteration, this takes as much additional time as the distance between fast and slow at time N, which is C-(N mod C). Since slow is moving from offset 0, this is also the offset where they meet.

So, if N mod C is zero, the phase 1 stops after N iterations at the beginning of the cycle. Otherwise, phase 1 stops after N+C-(N mod C) iterations at offset C-(N mod C) into the cycle.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Ok, so phase 2: slow takes N more steps to get to the cycle, at which point fast (now moving 1 per time step) is at (C-(N mod C)+N) mod C = 0. So they meet at the beginning of the cycle after phase 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

For completeness, phase 3 computes the cycle length by moving once more through the cycle:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

回复收藏 0 原文

留一抹残留的笑 2024-09-10 14:37:23

通过上述所有分析，如果您是一个通过示例学习的人，我尝试写一个简短的分析和示例，以帮助解释其他人试图解释的数学。开始了！

分析：

如果我们有两个指针，一个比另一个快，并且将它们一起移动，它们最终将再次相遇以指示循环或为空以指示无循环。

要找到循环的起点，令 ...

m 为从 head 到循环起点的距离；
d 为循环中的节点数；
p1 是较慢指针的速度；
p2 是较快指针的速度，例如。 2 表示一次遍历两个节点。
观察以下迭代：

<前><代码> m = 0，d = 10：
p1 = 1: 0 1 2 3 4 5 6 7 8 9 10 // 0 表示循环开始
p2 = 2: 0 2 4 6 8 10 12 14 16 18 20
m = 1，d = 10：
p1 = 1：-1 0 1 2 3 4 5 6 7 8 9
p2 = 2：-1 1 3 5 7 9 11 13 15 17 19
m = 2，d = 10：
p1 = 1: -2 -1 0 1 2 3 4 5 6 7 8
p2 = 2：-2 0 2 4 6 8 10 12 14 16 18

从上面的示例数据中，我们可以很容易地发现，每当快指针和慢指针相遇时，它们距离循环开始点就有 m 步。要解决此问题，请将较快的指针放回头部，并将其速度设置为较慢的指针的速度。当它们再次相遇时，该节点就是循环的开始。

With all the above analysis, if you are a learn-by-example person, I tried to write up an short analysis and example that help explains the math everyone else attempted to explain. Here we go!

Analysis:

If we have two pointers, one faster than the other, and move them along together, they will eventually meet again to indicate a cycle or null to indicate no cycle.

To find the starting point of the cycle, let ...

m be the distance from head to the beginning of the cycle;
d be the number of nodes in the cycle;
p1 be the speed of the slower pointer;
p2 be the speed of the faster pointer, eg. 2 means steps through two nodes at a time.
Observe the following iterations:

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

From the above sample data, we can easily discover that whenever the faster and the slower pointers meet, they are m steps away from the start of the cycle. To solve this, put the faster pointer back at the head and set its speed to the speed of the slower pointer. When they meet again, the node is the start of the cycle.

回复收藏 0 原文

吃兔兔 2024-09-10 14:37:23

用图表来完成这个工作会有所帮助。我试图不用方程式来解释这个问题。

如果我们让兔子和乌龟跑一圈，兔子跑两次乌龟，那么一圈结束时，兔子和乌龟将落后一半。两圈结束时，兔子和乌龟本应跑一圈，然后它们相遇。这适用于所有速度，例如，如果兔子跑 3 次，兔子 1 圈等于乌龟的 1/3，因此在 3 圈结束时，兔子和乌龟将跑完 1 圈，然后它们相遇。
现在，如果我们在循环前 m 步启动它们，则意味着更快的兔子在循环中提前启动。因此，如果乌龟到达循环的起点，则兔子在循环中领先 m 步，当它们相遇时，兔子将在循环开始前 m 步。

回复收藏 0 原文

寄与心 2024-09-10 14:37:23

假设

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

我们有 2 个指针 A 和 B，A 以 1 倍速度运行，B 以 2 倍速度运行，两者都从头开始。

当A到达N[0]时，B应该已经在N[m]中。
（注：A用m步到达N[0]，B应该再往前m步）

然后，A再跑k步碰撞到B，
即A在N[k]处，B在N[m+2k]处
（注：B应该从N[m]开始运行2k步）

A分别在N[k]和N[m+2k]处与B碰撞，这意味着
k=m+2k，因此 k = -m

因此，要从 N[k] 循环回到 N[0]，我们还需要 m 个步骤。

简单地说，我们只需要在找到碰撞节点后再运行m步即可。我们可以有一个从头开始运行的指针和一个从碰撞节点开始运行的指针，它们将在 m 步后在 N[0] 处相遇。

因此，伪代码如下：

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

lets say,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

we have 2 pointers A and B, A runs at 1x speed, B at 2x speed, both start at the beginning.

when A reaches N[0], B should be already in N[m].
(Note: A uses m steps to reach N[0], and B should be m steps further)

Then, A runs k more steps to collide to B,
i.e. A is at N[k], B is at N[m+2k]
(Note: B should runs for 2k steps starting from N[m])

A collide B at N[k] and N[m+2k] respectively, it means
k=m+2k, thus k = -m

Thus, to cycle back to the N[0] from N[k], we need m more steps.

Simply saying, we just need to run m more steps after we found the collision node. We can have a pointer to run from beginning and a pointer running from collision node, they will meet at N[0] after m steps.

Therefore, the pseudo code are as follow:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

回复收藏 0 原文

指尖上的星空 2024-09-10 14:37:23

我不这么认为，当他们相遇时，那就是起点。但是，是的，如果另一个指针（F）位于之前的交汇点，那么该指针将位于循环的末尾而不是循环的开头，并且从列表开头开始的指针（S）将位于循环的末尾，而不是循环的开头。结束于循环的开始处。例如：

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}

I don't think so its true that when they meet that's the starting point. But yes if the other pointer(F) was at the meeting point before , than that pointer will be at the end of the loop instead of the start of the loop and the pointer(S) which started from the start of the list it will end up at the start of the loop. for eg:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}

回复收藏 0 原文

如何在循环链表中找到循环起始节点？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（22）

关于作者

相关话题

热门标签

推荐作者

苦中寻乐

lueluelue

嗼ふ静

王权女流氓

与花如笺

残酷

友情链接

如何在循环链表中找到循环起始节点？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（22）

关于作者

相关话题

热门标签

推荐作者

苦中寻乐

lueluelue

嗼ふ静

王权女流氓

与花如笺

残酷

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。