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

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 , the length of the loop be and the ratio of fast-runner to slow-runner speed be .

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

So, the distance slow-runner travels is equal to . The distance the fast-runner travels is . But, fast-runner would also have traveled a distance ( times the distance of the slow-runner).

Therefore, we get . .

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

For greatest efficiency, (the slow pointer shouldn’t have traveled the loop more than once.)

therefore, Since is the no.of times the fast pointer has completed the loop, . For greatest efficiency, .

therefore .

If we take a value of , 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);