Detecting Cycles in Linked Lists

Welcome back! In our last lesson, we mastered the three-pointer technique for reversing a linked list in place. That exercise was a great warm-up in careful pointer manipulation. Today, we'll tackle another classic linked list problem that requires a different, but equally elegant, pointer-based strategy.

Our goal for this lesson is to solve the problem of cycle detection. How can you determine if a linked list contains a cycle—that is, if a node's next pointer refers back to a previous node in the list? A naive traversal would get stuck in an infinite loop. We'll learn a clever and highly efficient method to solve this, known as the slow and fast pointer technique. This pattern is a fundamental tool in algorithm design, and mastering it will add a powerful new approach to your problem-solving toolkit.

By the end of this lesson, you will be able to use slow and fast pointers to detect a cycle in a linked list with optimal space complexity.

The Problem: An Infinite Loop in Disguise

A cycle occurs in a linked list if, by following the next pointers, you eventually return to a node you've already visited. For example: 1 -> 2 -> 3 -> 4 -> 2. Here, node 4's next pointer creates a cycle by pointing back to node 2.

If you tried to traverse this list with a simple while (node !== null) loop, your code would run forever, cycling through 2 -> 3 -> 4 -> 2 -> 3 -> 4.... How can we detect this behavior without getting trapped?

A Simple but Space-Intensive Solution

A natural first thought is to keep a record of every node we've visited. As we traverse the list, we can add each node to a Set. Before visiting a node, we check if it's already in our set. If it is, we've found a cycle. If we reach the end of the list (null) without finding a repeat, there is no cycle.

This approach works perfectly and is a great "brute force" starting point in an interview. However, it requires extra memory to store the visited nodes. In the worst case, we might have to store every single node, leading to a space complexity of $O(n)$. Interviewers will often ask for a follow-up: can you do it with constant, $O(1)$, space?

The following video introduces the problem and explains this hash set-based solution.

The Fast and Slow Pointer Pattern

To achieve $O(1)$ space, we need a method that doesn't rely on an external data structure. This is where the fast and slow pointer pattern comes in. It's also known as Floyd's Cycle-Finding Algorithm or the "Tortoise and Hare" algorithm.

The idea is simple and elegant:

1. Create two pointers, slow and fast, both starting at the head of the list.
2. In each step of a loop, move slow one node forward (slow = slow.next).
3. In the same step, move fast two nodes forward (fast = fast.next.next).

Think of two runners on a track. If the track is a straight line, the faster runner will simply reach the end first. But if the track is circular, the faster runner will eventually lap the slower runner. The same logic applies here.

• If there is no cycle: The fast pointer will reach the end of the list (null) first.
• If there is a cycle: The fast pointer will enter the cycle first, followed by the slow pointer. Eventually, the fast pointer will catch up to and meet the slow pointer at the same node.

The image below illustrates this process.

Why Are They Guaranteed to Meet?

It's clear that if the fast pointer reaches null, there's no cycle. But if there is a cycle, are the two pointers guaranteed to meet? What if the fast pointer "jumps over" the slow one?

They are, in fact, guaranteed to meet. Once both pointers are inside the cycle, the fast pointer gains on the slow pointer by exactly one position with each iteration. Imagine the slow pointer is at position i and the fast pointer is at position j in the cycle. After one step, slow is at i+1 and fast is at j+2. The distance between them, which was j-i, is now (j+2) - (i+1) = j-i+1. But since they are in a cycle, distances are modular. The relative distance between them closes by one at each step. Because the distance is always an integer, it will eventually become 0, meaning they are at the same node.

The NeetCode video provides an outstanding and highly intuitive visual explanation for why this is always true.

Implementation in TypeScript

The implementation is surprisingly concise. The main challenge is correctly handling the loop condition to prevent errors when the fast pointer nears the end of the list.

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

function hasCycle(head: ListNode | null): boolean {
  if (!head) {
    return false;
  }

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

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

    if (slow === fast) {
      return true; // Cycle detected
    }
  }

  return false; // Fast pointer reached the end, no cycle
}

The loop condition while (fast !== null && fast.next !== null) is critical. We must check both fast and fast.next because we need to access fast.next.next. If fast is the last node, fast.next will be null, and trying to access fast.next.next would throw an error. This check ensures we can safely advance the fast pointer.

The following video provides a walkthrough of the implementation in JavaScript, with a particularly good explanation of this loop condition.

This algorithm runs in $O(n)$ time because, in the worst case, each node is visited a constant number of times. Crucially, its space complexity is $O(1)$, as we only use two pointers regardless of the list's size.

To solidify your understanding, it's helpful to review some common mistakes developers make when implementing this algorithm.

Extension: Finding the Start of the Cycle

A common follow-up question is not just to detect a cycle, but to find the exact node where the cycle begins. Floyd's algorithm has a second phase for this. The proof is a bit more mathematical, but the procedure is simple:

1. Detect the cycle and find the meeting point as we've already done.
2. Reset one pointer (e.g., slow) back to the head of the list. Leave the fast pointer at the meeting point.
3. Move both pointers one step at a time. The node where they meet again is the start of the cycle.

This works because it can be shown that the distance from the head to the cycle start is equal to the distance from the meeting point to the cycle start (plus some number of full cycle loops).

This is a powerful extension of the pattern. You can explore the intuition behind it in the following reading.

Conclusion

Today you've added a major pattern to your algorithmic repertoire. The slow and fast pointer technique is an ingenious way to solve problems involving cycles or finding middle points in sequences, all while maintaining constant space complexity.

Here are the key takeaways:

• The Problem: Detecting a cycle in a linked list efficiently is a classic problem. A hash set provides an $O(n)$ space solution, but we can do better.
• The Pattern: The "Tortoise and Hare" (slow and fast pointers) algorithm uses two pointers moving at different speeds (1x and 2x).
• The Logic: If the pointers meet, a cycle exists. If the fast pointer reaches null, the list is linear.
• The Guarantee: The pointers are guaranteed to meet inside a cycle because the fast pointer closes the distance to the slow pointer by one node per iteration.
• Complexity: This algorithm achieves the optimal $O(1)$ space complexity with $O(n)$ time complexity.

In our next lesson, we will move on to another fundamental data structure: the stack. We'll see how its Last-In, First-Out (LIFO) property makes it perfect for solving problems like validating properly nested parentheses.