Why increase pointer by two while finding loop in linked list, why not 3,4,5?

Solution 1:

From a correctness perspective, there is no reason that you need to use the number two. Any choice of step size will work (except for one, of course). However, choosing a step of size two maximizes efficiency.

To see this, 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!

Solution 2:

Let us suppose the length of the list which does not contain the loop be s, length of the loop be t and the ratio of fast_pointer_speed to slow_pointer_speed be k.

Let the two pointers meet at a distance j from the start of the loop.

So, the distance slow pointer travels = s + j. Distance the fast pointer travels = s + j + m * t (where m is the number of times the fast pointer has completed the loop). But, the fast pointer would also have traveled a distance k * (s + j) (k times the distance of the slow pointer).

Therefore, we get k * (s + j) = s + j + m * t.

s + j = (m / k-1)t.

Hence, from the above equation, length the slow pointer travels is an integer multiple of the loop length.

For greatest efficiency , (m / k-1) = 1 (the slow pointer shouldn't have traveled the loop more than once.)

therefore , m = k - 1 => k = m + 1

Since m is the no.of times the fast pointer has completed the loop , m >= 1 . For greatest efficiency , m = 1.

therefore k = 2.

if we take a value of k > 2 , more the distance the two pointers would have to travel.

Hope the above explanation helps.

Solution 3:

Consider a cycle of size L, meaning at the kth element is where the loop is: x_k -> x_k+1 -> ... -> x_k+L-1 -> x_k. Suppose one pointer is run at rate r₁=1 and the other at r₂. When the first pointer reaches x_k the second pointer will already be in the loop at some element x_k+s where 0 <= s < L. After m further pointer increments the first pointer is at x_{k+(m mod L)} and the second pointer is at x_{k+((m*r2+s) mod L)}. Therefore the condition that the two pointers collide can be phrased as the existence of an m satisfying the congruence

m = m*r₂ + s (mod L)

This can be simplified with the following steps

m(1-r₂) = s (mod L)

m(L+1-r₂) = s (mod L)

This is of the form of a linear congruence. It has a solution m if s is divisible by gcd(L+1-r₂,L). This will certainly be the case if gcd(L+1-r₂,L)=1. If r₂=2 then gcd(L+1-r₂,L)=gcd(L-1,L)=1 and a solution m always exists.

Thus r₂=2 has the good property that for any cycle size L, it satisfies gcd(L+1-r₂,L)=1 and thus guarantees that the pointers will eventually collide even if the two pointers start at different locations. Other values of r₂ do not have this property.

Solution 4:

If the fast pointer moves 3 steps and slow pointer at 1 step, it is not guaranteed for both pointers to meet in cycles containing even number of nodes. If the slow pointer moved at 2 steps, however, the meeting would be guaranteed.

In general, if the hare moves at H steps, and tortoise moves at T steps, you are guaranteed to meet in a cycle iff H = T + 1.

Consider the hare moving relative to the tortoise.

• Hare's speed relative to the tortoise is H - T nodes per iteration.

• Given a cycle of length N =(H - T) * k, where k is any positive integer, the hare would skip every H - T - 1 nodes (again, relative to the tortoise), and it would be impossible to for them to meet if the tortoise was in any of those nodes.

• The only possibility where a meeting is guaranteed is when H - T - 1 = 0.

Hence, increasing the fast pointer by x is allowed, as long as the slow pointer is increased by x - 1.