## [f]izzbuzzer

### 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

public class LinkedListCycle {
private static class Node {
public Node next = null;
public T data;

public Node(T data) {
this.data = data;
}
}

public static boolean detect(Node head) {

// a -> b -> a
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
}

if (slow == fast) {
return true;
}
}

return false;
}

public static void main(String[] args) {
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);