在链表中找到循环的开始节点? [英] finding the beginning node of a loop in a linked list?

问题描述

如何在给定的链表中找到循环的开始节点?我们称之为循环点

How to find the beginning node of a loop in a given linked list ? Let's call this the cycle point

到目前为止，我已经了解以下内容(使用慢/快指针):

So far, I've understand the following (using slow/fast pointer):

1. 假设列表有一个大小为 k
的非循环部分
2. 慢动作k步
3. 快速移动 2k 步
4. 快是 (2k - k)= k 步 ahead 慢
5. slow 在循环开始处；也称为循环点
6. fast 是 (LOOP_LENGTH - k) 步 behind 从 Cycle point 或慢速指针在这一点
7. 每慢走 1 步，快走 2 步，慢走 1 步.
8. 因此，需要快速的(LOOP_LENGTH - k) 步才能遇到慢速碰撞
9. 这是我不明白的步骤:在这个碰撞点，两个节点都离循环前面k步.
10. 找到碰撞点后，将一个指针移到列表的头部.
11. 现在以 1 步/转的速度移动两个指针直到发生碰撞.它们相遇的节点是循环的开始，因此是循环点

1. Assume list has a non-looped part of size k
2. slow moves k steps
3. fast moves 2k steps
4. fast is (2k - k)= k steps ahead of slow
5. slow is at the beginning of loop; also known as Cycle point
6. fast is (LOOP_LENGTH - k) steps behind from Cycle point or slow pointer at this point
7. for each 1 step slow moves, fast moves 2 steps and gains on slow by 1 step.
8. Thus, it would take fast (LOOP_LENGTH - k) steps to meet slow and collide
9. This is the step I don't understand: At this collision point, both nodes will be k steps from the front of the loop.
10. Once the collision point is found, move one pointer to the head of list.
11. Now move both pointers at the speed of 1 step / turn till the collide. The node at which they both meet is the beginning of the the loop and hence the Cycle point

有人可以向我解释第 9 步和之后的内容吗?

Can someone please explain me step 9 and after that ?

谢谢

编辑:

我想指出的一件事是，一旦进入循环，fast 永远不会超过慢指针.他们会碰撞.原因如下:slow 在 i 处，fast 假定在 i-1 处.当它们移动时，slow=> i+1 和 fast 也将在 i+1 处，因此发生碰撞.或者，慢在 i 处，快在 i-2 处.下一步，慢-> i+1；快:我.下一步，慢-> i+2，快:i+2，因此再次碰撞.这么快永远追不上慢，循环内只能碰撞一次！

One thing I'd like to point out is, once inside the loop, fast will never overtake slow pointer. They will collide. Here's why: slow is at i and fast is assuming at i-1. when they move, slow=> i+1 and fast will be at i+1 too, hence collision. OR, slow is at i and fast is at i-2. next move, slow-> i+1; fast: i. next move, slow-> i+2, fast: i+2 and hence collision again. so fast will never be able to overtake slow, only collide once inside the loop!

推荐答案

你的6.错了，快指针离慢指针还有k步，慢指针在那个时候处于循环点；但最好使用ahead 或 behind 而不是 away.另外，k 可能更小、更大或等于 loop_length.

Your 6. is wrong, the fast pointer is still k steps away from the slow pointer which is at the cycle point at that time; but better use ahead or behind instead of away. Plus, k may be smaller, bigger, or equal to the loop_length.

因此，当到达循环点时，快速指针比慢指针领先 k 步，在您的假设下，循环点是开始后的 k 步.现在，在循环上进行测量，快速指针比循环点提前 k % loop_length 步.对?如果k = some_n * loop_length + r，则快速指针比循环点领先r步，也就是说，r := k % loop_length 领先一步.

So, the fast pointer is k steps ahead of a slow one when that's reached the loop point which is, at your supposition, k steps after the start. Now, measuring on a loop, the fast pointer is k % loop_length steps ahead of the loop point. Right? If k = some_n * loop_length + r, the fast pointer is r steps ahead of the loop point, which is to say, r := k % loop_length steps ahead.

但这意味着慢指针是loop_length - r 步在快速指针之前，沿着循环.毕竟这是一个循环.因此，在 loop_length - r 附加步骤之后，快速指针将赶上慢速指针.每走一步，慢指针移开，快指针移近 两 步.

But that means that the slow pointer is loop_length - r steps ahead of the fast one, along the loop. This is a loop after all. So after loop_length - r additional steps the fast pointer will catch on to the slow one. For each step the slow pointer moves away, the fast moves closer in by two steps.

所以我们不知道k，我们不知道loop_length 或r，我们只知道m = k+ loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length.直到两个指针相遇点的总步数 m 是循环长度的倍数.

So we don't know k, we don't know loop_length or r, we only know m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length. The total number of steps m until the two pointers' meeting point, is a multiple of the loop length.

所以现在我们重新开始，在开始处有一个新的指针，慢的遇到快的，m 比新的领先一步.我们以相同的速度移动新的和慢的，每次移动 1 步，并且在循环点它们会相遇 - 因为当新指针到达循环点时，第二个仍然是 m向前迈进，也就是说，m % loop_length == 0 沿着循环向前迈进.这样我们就能找出 k 是什么(我们一直在计算我们的步数)，以及循环点.

So now we start over, with a new pointer at the start and the slow where it met the fast, m steps ahead of the new. We move the new and the slow at equal speed, by 1 step at each time, and at the cycle point they shall meet - because when the new pointer has reached the cycle point, the second is still m steps ahead, which is to say, m % loop_length == 0 steps ahead along the loop. That way we find out what k is (we count our steps all the time), and the cycle point.

我们再循环一次找到loop_length，直到两者再次相遇.

And we find loop_length by going along the loop one more time, until the two meet one more time.

• 另见:http://en.wikipedia.org/wiki/Cycle_detection#Algorithms

这篇关于在链表中找到循环的开始节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！