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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
public class LinkedListCycle { private static class Node<T> { public Node next = null; public T data; public Node(T data) { this.data = data; } } public static boolean detect(Node<Integer> head) { Node<Integer> slow = head; Node<Integer> 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<Integer> head = new Node(1); Node<Integer> node2 = new Node(2); Node<Integer> node3 = new Node(3); Node<Integer> node4 = new Node(4); Node<Integer> node5 = new Node(5); Node<Integer> 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)); } } |