为什么由两个增加的指针，同时寻找在循环链表，为什么不3,4,5？ [英] Why increase pointer by two while finding loop in linked list, why not 3,4,5?

问题描述

我看了一下<一href="http://stackoverflow.com/questions/2663115/interview-question-how-to-detect-a-loop-in-a-linked-list">question这已经谈算法寻找循环链表中。我已阅读的解决方案，在很多的，我们必须采取两个指针地提到弗洛伊德的循环查找算法。一个指针（较慢/龟）增加一和其他指针（快/野兔）增加2。当它们相等，我们发现在循环和时更快地指针到达空有链表中没有环路。

现在我的问题是，为什么我们增加更快的指针由2.为什么不是别的东西？由2提高是必要的，或者我们可以用X增加它来获得结果。是否有必要，我们会找到一个循环，如果我们增加更快的指针由2个或可能存在的情况下，我们需要增加3或5或x。

解决方案

没有理由，你需​​要使用两个数。步长任何选择就可以了（当然，除了一个，）。

要明白为什么这个工程，让我们来看看为什么Floyd的算法的工作摆在首位。我们的想法是想想序列x <子> 0 ，X <分> 1 ，X ₂ ，...，X <子> N ，......。如果该列表不包含一个周期，那么所有这些值是不同的。如果它包含一个周期，但是，那么这个顺序将重复不休。

下面是使弗洛伊德的算法的工作原理：

  

的链接的列表包含一个周期，当且仅当有一个正整数j，使得对于任何正整数k中，x <子>Ĵ = X <子> JK

让我们去证明这一点;它并不难。对于如果的情况下，如果这样的AJ存在，挑K = 2。然后我们有一些积极的Ĵ，X <子>Ĵ = X <子> 2J 和J＆NE; 2j上，因此该列表包含一个周期。

有关的另一个方向，假定列表包含长度升起始位置S的一个周期。令j为L大于S的最小倍数。那么对于任意k，如果我们考虑x <子>Ĵ和X <子> JK ，因为j是环路长度的倍数，我们可以认为出现x <子> JK 如由起始位置j在列表中，然后取Ĵ形成的元件的步骤K-1次。但是，这些时候你采取Ĵ步骤，你最终又回到开始的地方，在列表中，因为j是环路长度的倍数。因此，X <子>Ĵ = X <子> JK 。

这证明保证你，如果你需要在每个迭代步骤的任何常数，你的确会打慢指针。更多precisely，如果你正在考虑在每次迭代k步，那么你最终会发现积点X <子>Ĵ和X <子> KJ 和将检测周期。直观地说，人们倾向于选择K = 2，尽量减少运行时间，因为你需要在每次迭代的最少的步骤。

我们可以更正式如下分析运行时间。如果该列表不包含一个周期，然后快速指针将击中n步后的列表中为O（n）的时间，其中n是列表中的元素的数量的末端。否则，这两个指针将满足后缓慢指针已采取Ĵ步骤。请记住，j是升大于S的最小倍数。如果S＆乐;升，则j = 1;否则如果s>升，则j将最多2秒，因此j的值是O（S + 1）。自升和s不能大于列表中的元素的数量较大，这意味着比J =为O（n）。然而，在缓慢指针已采取Ĵ步骤，快速指针将采取k步为每个所采取的较慢指针因此它将采取O（KJ）步第j步骤。由于J = O（N），净运行时间最多为O（NK）。请注意，此说，我们采取与快速指针更多的步骤，时间越长，算法需要完成（虽然只是按比例等等）。采摘K = 2从而最大限度地减少了算法的整体运行。

希望这有助于！

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.

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).

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.

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

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.

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.

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.

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.

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.

Hope this helps!

这篇关于为什么由两个增加的指针，同时寻找在循环链表，为什么不3,4,5？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！