# Linked list cycle II

From the problem of the same name in LeetCode. The problem statement is:

Given a linked list, return the node where the cycle begins. If there is no cycle, return

null.

In our minds we visualise a loop with a straight line attached to it.
The straight line being the linked list before the cycle starts.
Let us call the length of the cycle *k*.

Imagine further that we set off two pointers from the head with one moving twice as fast as the other.
If the two pointers collide in future at time *t* then we know two things:-

- The slow pointer is
*t*away from the head of the list. - The fast pointer is
*t*ahead of the slow pointer.

The fact that the slow and fast pointer have collided means that they are some multiple of *s* apart.
So the second observation actually tells us that *t=ks*.

If *l* is the length of the straight line before the cycle then *l=l+t*.
This means that if we start a pointer at head and a pointer at the *t* th node then their first collision will be the first node in the cycle.

So the code to complete the question is quite straightforward:

public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return null; } ListNode slow = head.next; ListNode fast = head.next.next; while (!slow.equals(fast)) { if (fast.next == null || fast.next.next == null) { return null; } fast = fast.next.next; slow = slow.next; } slow = head; while (!slow.equals(fast)) { fast = fast.next; slow = slow.next; } return slow; } }