Hoarding programming problems for you!

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Given a linked list, determine if it has a cycle in it

Sharing is caring!

Problem statement
Given a linked list, determine if it has a cycle in it.

For the solution we are going to use a technique known as the two-pointer technique. That is we will involve two pointers: one slow-runner and the other fast-runner. The slow-runner will move forward 1 list node at the time while the fast-runner will move forward 2 nodes at a time. If the two pointers ever meet, then we know that the list contains a cycle. Otherwise there is no cycle in the list.

Why does this work
Let us suppose the length of the list which does not contain the loop be s, the length of the loop be t and the ratio of fast-runner to slow-runner speed be k.

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

So, the distance slow-runner travels is equal to s + j. The distance the fast-runner travels is s + j + m * t. But, fast-runner would also have traveled a distance k * (s + j) (k times the distance of the slow-runner).

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

s + j = \frac{m}{k-1}t.

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

For greatest efficiency, \frac{m}{k-1} = 1 (the slow pointer shouldn’t have traveled the loop more than once.)

therefore, m = k - 1 \rightarrow k = m + 1

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

therefore k = 2.

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