Fast & Slow Pointers (Floyd's Cycle Detection)

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. The Tortoise and the Hare

The Fast and Slow Pointer Pattern (also known as Floyd's Cycle-Finding Algorithm) uses two pointers that traverse a sequence at different speeds:

• Slow Pointer (slow): Advances 1 step at a time.
• Fast Pointer (fast): Advances 2 steps at a time.

2. Why It Matters

If a cycle exists in a linked list or sequence, the fast pointer will eventually loop around and lap the slow pointer, meeting at the exact same node in $O(N)$ time and $O(1)$ space without storing visited nodes in a hash set!

3. Detecting Cycles in a Linked List

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head) {
  if (!head || !head.next) return false;

  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // Move 1 step
    fast = fast.next.next;   // Move 2 steps

    if (slow === fast) {
      return true; // Fast pointer caught up to slow pointer (Cycle detected!)
    }
  }

  return false; // Fast pointer reached end of list (No cycle)
}

4. Finding the Middle Node of a List

When the fast pointer reaches the end of the list, the slow pointer is guaranteed to be at the exact middle node:

function findMiddleNode(head) {
  let slow = head;
  let fast = head;

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

  return slow; // Points to the middle element!
}

5. Common Mistakes

• Null Pointer Dereference: Checking only while (fast.next !== null) causes a crash when fast is null. Always check BOTH while (fast !== null && fast.next !== null).

6. Next Steps

Use fast and slow pointers for list cycles and midpoints. Next, let's explore the Sliding Window Pattern!