fizzbuzzer.com

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.

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

Code