Fast and slow pointers

Overview

The fast and slow pointers technique (Floyd's tortoise and hare) moves two pointers through a sequence at different speeds, usually one step and two steps. If there is a cycle, the fast pointer eventually laps the slow one and they meet. If there is no cycle, the fast pointer reaches the end first.

The same idea finds the middle of a list in one pass (when fast reaches the end, slow is halfway), the start of a cycle, and duplicate numbers in arrays whose values act as next pointers. It uses O(1) extra memory, which is why interviewers love it as a follow-up to hash-set solutions.

When to use it

• Detect a cycle in a linked list or in any sequence x -> f(x).
• Find the middle node, or split a list into halves.
• Find where a cycle begins.
• O(1) space is required where a visited set would otherwise be used.
• Find the kth node from the end (a fixed gap variant).

Problem patterns it solves

Where it is used in real software

Key terms

Tortoise (slow)

Moves one step per iteration.

Hare (fast)

Moves two steps per iteration.

Meeting point

Where slow and fast coincide inside a cycle.

Cycle entry

First node of the cycle; found by resetting one pointer to the head.

Functional graph

Each value points to exactly one next value, e.g. i -> nums[i].

Floyd's algorithm for the cycle start

1. 1
   Phase 1: detect

   slow = slow.next, fast = fast.next.next until they meet (cycle) or fast reaches null (no cycle).

2. 2
   Phase 2: reset

   Move one pointer back to the head. Keep the other at the meeting point.

3. 3
   Move both one step at a time

   They meet exactly at the cycle entry.

4. 4
   Why it works

   If the distance from head to the entry is a and the meeting point is b steps into a cycle of length c, then 2(a + b) = a + b + kc, so a = kc - b. Walking a steps from the meeting point lands on the entry.

Find the duplicate number with O(1) space

nums = [1, 3, 4, 2, 2]; treat index -> nums[index] as a next pointer

The duplicate value is where two indexes point, which is the entry of the cycle. O(n) time and O(1) space, without modifying the array.

Implementation

1function hasCycle(head) {2  let slow = head, fast = head;3  while (fast && fast.next) {4    slow = slow.next;5    fast = fast.next.next;6    if (slow === fast) return true;7  }8  return false;9}10 11function detectCycle(head) {12  let slow = head, fast = head;13  while (fast && fast.next) {14    slow = slow.next;15    fast = fast.next.next;16    if (slow === fast) {17      slow = head; // phase 218      while (slow !== fast) {19        slow = slow.next;20        fast = fast.next;21      }22      return slow;23    }24  }25  return null;26}27 28function middleNode(head) {29  let slow = head, fast = head;30  while (fast && fast.next) {31    slow = slow.next;32    fast = fast.next.next;33  }34  return slow; // second middle for even lengths35}36 37function findDuplicate(nums) {38  let slow = nums[0], fast = nums[0];39  do {40    slow = nums[slow];41    fast = nums[nums[fast]];42  } while (slow !== fast);43  slow = nums[0];44  while (slow !== fast) {45    slow = nums[slow];46    fast = nums[fast];47  }48  return slow;49}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Checking only fast.next.

  Fix: The loop condition must be fast && fast.next, in that order.

• Comparing values instead of node references.

  Fix: Use slow === fast; different nodes can hold equal values.

• Wrong start in findDuplicate.

  Fix: Start both at nums[0] and use a do-while so they move before comparing.

Interview questions

Practice problems