# 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) { Node slow = head; Node fast = 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 head = new Node(1); 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); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node3; System.out.println(detect(head)); } }