Linked list cycle II

Back to index

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

  1. The slow pointer is t away from the head of the list.
  2. 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;
  }
}