为什么在链表中查找循环时将指针增加 2，为什么不是 3、4、5? [英] Why increase pointer by two while finding loop in linked list, why not 3,4,5?

问题描述

我看了问题 已经讨论了在链表中查找循环的算法.我已经阅读了 Floyd 的循环寻找算法 解决方案，在很多地方都提到了我们必须拿两个指针.一个指针(slow/tortoise)增加一个，另一个指针(faster/hare)增加2.当它们相等时，我们找到循环，如果faster指针达到空，链表中就没有循环.

I had a look at question already which talk about algorithm to find loop in a linked list. I have read Floyd's cycle-finding algorithm solution, mentioned at lot of places that we have to take two pointers. One pointer( slower/tortoise ) is increased by one and other pointer( faster/hare ) is increased by 2. When they are equal we find the loop and if faster pointer reaches null there is no loop in the linked list.

现在我的问题是为什么我们将更快的指针增加 2.为什么不是别的?增加 2 是必要的，或者我们可以增加 X 以获得结果.如果我们将更快的指针增加2，我们是否有必要找到一个循环，或者我们需要增加3或5或x的情况.

Now my question is why we increase faster pointer by 2. Why not something else? Increasing by 2 is necessary or we can increase it by X to get the result. Is it necessary that we will find a loop if we increment faster pointer by 2 or there can be the case where we need to increment by 3 or 5 or x.

推荐答案

您没有理由需要使用第二个.任何步长选择都可以(当然，除了一个).

There is no reason that you need to use the number two. Any choice of step size will work (except for one, of course).

要了解为什么会这样，让我们​​首先看看为什么 Floyd 的算法会起作用.这个想法是考虑序列 x₀, x₁, x₂, ..., x_n, ... 如果您从列表的开头开始，然后继续沿着它走，直到到达结尾，您将访问的链接列表的元素.如果列表不包含循环，则所有这些值都是不同的.但是，如果它确实包含一个循环，那么这个序列将无休止地重复.

To see why this works, let's take a look at why Floyd's algorithm works in the first place. The idea is to think about the sequence x₀, x₁, x₂, ..., x_n, ... of the elements of the linked list that you'll visit if you start at the beginning of the list and then keep on walking down it until you reach the end. If the list does not contain a cycle, then all these values are distinct. If it does contain a cycle, though, then this sequence will repeat endlessly.

这是使 Floyd 算法起作用的定理:

Here's the theorem that makes Floyd's algorithm work:

链表包含一个循环当且仅当存在一个正整数 j 使得对于任何正整数 k，x_j = x_jk.

The linked list contains a cycle if and only if there is a positive integer j such that for any positive integer k, x_j = x_jk.

让我们去证明这一点；这并不难.对于if"情况，如果这样的 j 存在，选择 k = 2.然后我们有一些正 j，x_j = x_2j 和 j ≠2j，所以列表包含一个循环.

Let's go prove this; it's not that hard. For the "if" case, if such a j exists, pick k = 2. Then we have that for some positive j, x_j = x_2j and j ≠ 2j, and so the list contains a cycle.

对于另一个方向，假设列表包含从位置 s 开始的长度为 l 的循环.设 j 是 l 大于 s 的最小倍数.那么对于任何k，如果我们考虑x_j和x_jk，因为j是循环长度的倍数，我们可以想到x_jk 作为从列表中的位置 j 开始，然后走 j 步 k-1 次形成的元素.但是每次您执行 j 步时，您都会回到列表中开始的位置，因为 j 是循环长度的倍数.因此，x_j = x_jk.

For the other direction, assume that the list contains a cycle of length l starting at position s. Let j be the smallest multiple of l greater than s. Then for any k, if we consider x_j and x_jk, since j is a multiple of the loop length, we can think of x_jk as the element formed by starting at position j in the list, then taking j steps k-1 times. But each of these times you take j steps, you end up right back where you started in the list because j is a multiple of the loop length. Consequently, x_j = x_jk.

这个证明向你保证，如果你在每次迭代中采取任何固定数量的步骤，你确实会遇到慢指针.更准确地说，如果您在每次迭代中采取 k 步，那么您最终将找到点 x_j 和 x_kj 并检测循环.直觉上，人们倾向于选择 k = 2 来最小化运行时间，因为每次迭代的步骤数最少.

This proof guarantees you that if you take any constant number of steps on each iteration, you will indeed hit the slow pointer. More precisely, if you're taking k steps on each iteration, then you will eventually find the points x_j and x_kj and will detect the cycle. Intuitively, people tend to pick k = 2 to minimize the runtime, since you take the fewest number of steps on each iteration.

我们可以更正式地分析运行时如下.如果列表不包含循环，则快速指针将在 O(n) 时间的 n 步后到达列表的末尾，其中 n 是列表中的元素数.否则，慢指针走j步后，两个指针会相遇.请记住，j 是 l 大于 s 的最小倍数.如果 s ≤l, 那么 j = l;否则，如果 s > l，则 j 最多为 2s，因此 j 的值为 O(s + l).由于 l 和 s 不能大于列表中的元素数，这意味着 j = O(n).然而，在慢指针走了 j 步之后，对于慢指针所走的 j 步中的每一步，快指针都将采取 k 步，因此它将采取 O(kj) 步.由于 j = O(n)，净运行时间最多为 O(nk).请注意，这表示我们对快速指针采取的步骤越多，算法完成所需的时间就越长(尽管只是按比例如此).选择 k = 2 从而最小化算法的整体运行时间.

We can analyze the runtime more formally as follows. If the list does not contain a cycle, then the fast pointer will hit the end of the list after n steps for O(n) time, where n is the number of elements in the list. Otherwise, the two pointers will meet after the slow pointer has taken j steps. Remember that j is the smallest multiple of l greater than s. If s ≤ l, then j = l; otherwise if s > l, then j will be at most 2s, and so the value of j is O(s + l). Since l and s can be no greater than the number of elements in the list, this means than j = O(n). However, after the slow pointer has taken j steps, the fast pointer will have taken k steps for each of the j steps taken by the slower pointer so it will have taken O(kj) steps. Since j = O(n), the net runtime is at most O(nk). Notice that this says that the more steps we take with the fast pointer, the longer the algorithm takes to finish (though only proportionally so). Picking k = 2 thus minimizes the overall runtime of the algorithm.

希望这有帮助！

这篇关于为什么在链表中查找循环时将指针增加 2，为什么不是 3、4、5?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！