Solution: Slow and Fast Pointers

There was a small lake close to where I lived when I was an undergrad, and I used to go there with a friend to run around the lake. He was much more athletic than me, so he would run faster than me. We would start at the same point, and I would run at my pace, while he would run at his pace. After a while, he would have finished a lap, start a second lap, and eventually overtake me while I was still on the first lap.

Do you see where I am going with this? If we were running a straight line, he would keep getting farther and farther ahead of me, but because we are running in a circle, he will eventually catch up to me and pass me again. Now suppose we were dropped on a trail where we did not know if the trail was a loop or not. We would start running, and if it was not a loop, my friend would finish the trail, sit down, and wait for me to finish. But if it was a loop, he would eventually catch up to me again. We can use this idea to detect a cycle in a linked list.

We will make two pointers to represent me (the slow pointer) and my friend (the fast pointer). We need to give them different speeds, so we will make the slow pointer move one step at a time, and the fast pointer move two steps at a time. If there is no cycle, the fast pointer will reach the end of the list (null) before the slow pointer. In fact, if the fast pointer reaches the end of the list, it means there is no cycle, and we can return false. But if there is a cycle, the fast pointer will eventually catch up to the slow pointer, and we can return true.

Let’s try to implement this idea in code:

public static boolean hasCycle(ListItem head) {
  ListItem slow = head;
  ListItem fast = head;

  // we will build the solution step by step
}

Now we have the two pointers. Let’s start with the slow pointer. We want it to move one step at a time, so we can just do slow = slow.next in a loop.

while (slow != null) {
  slow = slow.next;
}

Now we need to move the fast pointer. We want it to move two steps at a time, so we can do fast = fast.next.next in the same loop. But we need to be careful here. If fast is null, or fast.next is null, then accessing fast.next.next throws a NullPointerException. So we need to check if fast and fast.next are not null before we move the fast pointer.

while (fast != null && fast.next != null) {
  fast = fast.next.next;
}

Now let’s combine the two loops. We know if there is no cycle, the fast pointer will reach the end of the list, so we let the fast pointer’s loop condition be the main loop condition. Inside the loop, we will move the slow pointer one step and the fast pointer two steps.

while (fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.next;
}

Now if there is a cycle, the fast pointer will eventually catch up to the slow pointer. We can check for this condition inside the loop.

while (fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.next;

  if (fast == slow) {
    return true;  // there is a cycle
  }
}

But if the fast pointer reaches the end of the list, it means there is no cycle, and we can return false after the loop. So here is the complete implementation:

public static boolean hasCycle(ListItem head) {
  ListItem slow = head;
  ListItem fast = head;

  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;

    if (fast == slow) {
      return true;  // there is a cycle
    }
  }

  return false;  // no cycle found
}

If the list is empty (head is null), both slow and fast will be null, and the loop will not execute, so it will return false, which is correct.

If the list has just one node, then there are two cases:

• If the single node does not point to itself (that is, its next is null), then fast.next is null from the start, so the loop does not execute and the method returns false, which is correct.
• If the single node points to itself, then fast and slow will both start at that node, and in the first iteration of the loop, fast will move two steps (which will bring it back to the same node), and slow will move one step (which will also bring it back to the same node), so they will be equal, and it will return true, which is correct.

For any other case, if there is a cycle, fast will eventually catch up to slow, and if there is no cycle, fast will reach the end of the list. So this implementation should work for all cases.

What is the complexity of this algorithm? The auxiliary space is $O(1)$ because we are only using a constant amount of extra space for the two pointers. So we stay within constant space.

• If there is no cycle, the fast pointer will traverse the entire list, jumping two steps at a time, which takes about $n/2$ loop iterations, which is $O(n)$.

• If there is a cycle, the slow pointer first traverses the part of the list before the cycle starts, which takes at most $n$ steps. From then on both pointers are inside the cycle. Each iteration, the distance between the fast pointer and the slow pointer decreases by one, because the fast pointer moves two steps and the slow pointer moves one. The gap between them is less than the length of the cycle, so they meet within one cycle length. Both the prefix and the cycle are made of nodes reachable from the head, so both are at most $n$, and the whole traversal is $O(n)$.

This is the third time we have used two pointers on a problem. In two sum with a sorted array, the two pointers started at opposite ends of the array and moved toward each other. In removing duplicates from a sorted array, a slow pointer and a fast pointer moved through the array in the same direction at different rates. Here the two pointers also move in the same direction at different rates, but over a linked list instead of an array, and what we check is whether they ever reach the same node. The details are different each time. But in all three cases we keep track of two positions in a single pass, and we get the answer by comparing those two positions instead of looking at just one.