Fast & Slow Pointers

MNEMONIC Hare laps the tortoise.

PATTERN Two speeds over one sequence

Place two cursors at the start of a sequence and advance them at different rates — classically fast += 2 and slow += 1. The “sequence” can be the .next arrows of a linked list, or an implicit successor function like i → nums[i] over array indices or x → digitSquareSum(x) over numbers.

Three questions fall out of this one setup, each with no auxiliary memory: does the sequence cycle, what is its middle, and where does a cycle begin.

KEY IDEA The gap closes by 1 each step

The fast cursor gains on the slow one by 2 − 1 = 1 position every beat. On a straight run this means the fast one finishes in half the steps, leaving the slow one at the midpoint. Inside a loop, the relative gap shrinks by 1 (mod the loop length) until it is 0 — a guaranteed collision. The fast cursor can never “leap over” the slow one, because their separation only ever changes by a single step.

COST O(n) time, O(1) space, one pass

The tortoise visits each node at most a constant number of times before the pointers meet or the hare exits, so the work is O(n). Only two pointers (plus, for phase 2, one reset cursor) are stored, so the extra space is O(1) regardless of input size.

VARIANTS Detect · middle · entrance

The same loop, three endings:

• Cycle detection. Return whether slow === fast ever holds during the loop. If the hare exits through null, there is no cycle.
• Find the middle. Drop the equality check entirely; when the loop ends (hare at the end), slow sits on the middle node.
• Cycle entrance (phase 2). After the collision, reset one pointer to the head and advance both by 1 — they re-meet exactly at the node where the loop begins. The same math powers find the duplicate number.

RUN IT Tortoise & hare: the hare laps the tortoise inside the loop

TRIGGERS When you see ___ → reach for ___

Reach for fast & slow when a problem walks a sequence and asks a distance or cyclicity question — and especially when it forbids extra memory. The sequence may be an explicit ListNode chain or an implicit next function over indices or numbers.

RED FLAGSWhen it's NOT this pattern

• You need to count nodes or address them by position.If the task is really “the k-th element” or “how many,” a plain array index or a single length pass is simpler than juggling two speeds.
• The successor isn't deterministic / single-valued. Floyd needs exactly one nextper state. If a node can branch (a tree or graph with out-degree > 1), use DFS/BFS with a visited set instead.
• You also need O(1) lookup, not just traversal.Problems like LRU Cache pair a list with a hash map — that's a combined structure, not a two-speed walk.

TEMPLATE Cycle detection (Floyd)

When → Any “does it loop?” question on a list — or on any single-successor sequence — where you want a yes/no in one pass and O(1) space.

// Shared node shape (used by the list templates below)
interface ListNode {
  val: number;
  next: ListNode | null;
}

// Floyd cycle DETECTION — O(n) time, O(1) space
// slow +1, fast +2. If they ever land on the same node, a cycle exists;
// if fast walks off the end (null), the list is acyclic.
function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {   // guard fast FIRST, then fast.next
    slow = slow!.next;        // tortoise: 1 hop
    fast = fast.next.next;    // hare: 2 hops
    if (slow === fast) return true;   // collision → cycle
  }
  return false;               // fell off the end → no cycle
}

TEMPLATE Find the middle

When → You need the midpointin a single pass — as an answer itself, or as the split point for “reverse the second half” problems (reorder list, palindrome).

// Shared node shape (used by the list templates below)
interface ListNode {
  val: number;
  next: ListNode | null;
}

// Find the MIDDLE in one pass — O(n) time, O(1) space
// When fast reaches the end, slow has gone exactly half the distance.
function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;        // +1
    fast = fast.next.next;    // +2
  }
  // ODD length  → slow is the exact middle.
  // EVEN length → slow is the SECOND of the two middles.
  // (Want the first middle instead? start fast = head.next.)
  return slow;
}

TEMPLATE Cycle entrance (Floyd phase 2)

When → You need where the loop begins, not just whether one exists. After detecting the collision, a reset-and-walk finds the entry node.

// Shared node shape (used by the list templates below)
interface ListNode {
  val: number;
  next: ListNode | null;
}

// Find the cycle ENTRANCE — Floyd phase 2, O(n) time, O(1) space
// Math: distance(head → entry) === distance(meeting → entry) around the loop.
function detectCycle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Phase 2: reset ONE pointer to head, then advance BOTH by 1.
      // They re-meet exactly at the loop's entrance node.
      let entry = head;
      while (entry !== slow) {
        entry = entry!.next;
        slow = slow!.next;
      }
      return entry;
    }
  }
  return null;                 // no cycle
}

TEMPLATE Array as a linked list (find the duplicate)

When → An array of n + 1 values in [1..n] with exactly one repeat, and you may not modify the array or use extra space. Treat i → nums[i] as a next pointer.

// Array as an implicit LINKED LIST — find the duplicate, O(n) time, O(1) space
// nums[i] is the "next" pointer of node i. With n+1 values in [1..n], two
// indices point at the same value → that value is a cycle ENTRANCE.
function findDuplicate(nums: number[]): number {
  let slow = nums[0];
  let fast = nums[0];

  // Phase 1: find a meeting point inside the cycle.
  do {
    slow = nums[slow];          // +1 hop:  i → nums[i]
    fast = nums[nums[fast]];    // +2 hops
  } while (slow !== fast);

  // Phase 2: walk one pointer from the start; they meet at the duplicate.
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;                  // the repeated value (the cycle entrance)
}

PITFALL Missing or mis-ordered null checks on fast && fast.next

The hare advances two steps, so before fast.next.next you must confirm fast !== null and then fast.next !== null — in that order. Checking only fast crashes on even-length lists (the hare lands on the last node); checking only fast.next crashes on an empty list. This is the single most common runtime error in the pattern.

PITFALL Even vs odd length: which node is the "middle"

With both pointers starting at head, odd-length lists leave slow on the exact middle, but even-length lists leave it on the second of the two middles. If the problem wants the first middle (e.g. to make the first half the longer one when splitting), start fast = head.next. Decide deliberately — don't discover it from a failing test.

PITFALL Forgetting the phase-2 reset for the cycle entrance

A frequent bug is returning the collision node as the loop start. It almost never is. Phase 2 is mandatory: set one pointer back to head, keep the other at the meeting point, then advance both by 1 until they are equal. Only then are you standing on the entrance.

PITFALL Off-by-one on where (and whether) they meet

For the array variant, advance before the first comparison — a do/while loop — or both pointers start equal at nums[0] and you exit instantly with a false positive. Likewise, never test slow === fast on the very first frame of detection: they begin together by construction. Step first, compare second.

PROBLEMS