Algorithms - 5. Fast and Slow Pointers

When to use Fast and Slow Pointers

Use Fast and Slow Pointers when you need to explore a linked list at different speeds to detect patterns or find specific positions. While most commonly used for cycle detection, it can be adapted for:

• Cycle detection (classic use case - Floyd's Cycle Detection)
• Finding the middle node of a linked list in one pass
• Finding the start of a cycle in a linked list
• Detecting the k-th node from the end (by maintaining a gap)
• Finding palindrome sequences in linked lists
• Any problem where comparing positions at different rates reveals hidden structure

Example problem

Defective Manufacturing Line: Imagine a circular conveyor belt in a factory where products move in a line. Some products might loop back to an earlier point due to a defect in the track.

Given a linked list representing products on the line: 1 → 2 → 3 → 4 → 5 → 3 (loops back), determine:

1. Is there a loop in the production line?
2. Where does the loop begin?

Answer: Yes, there's a loop, and it begins at node 3.

Single most important insight

Moving at different speeds guarantees meeting in a cycle - if two pointers traverse a linked list where one moves twice as fast as the other, they will eventually meet inside any cycle, while naturally stopping at the end if no cycle exists.

Mental note: The algorithm's genius lies in the speed differential. The fast pointer moves 2 steps while the slow pointer moves 1 step. In a cycle, this creates a "chase" where the fast pointer catches up to the slow pointer at a predictable rate. If there's no cycle, the fast pointer simply reaches the end first. This simple speed difference reveals cycle structure without extra memory.

Decision Framework

At every step in the traversal, the algorithm makes these simple checks:

• Has the fast pointer reached the end? (null or next is null) → No cycle exists
• Do fast and slow pointers point to the same node? → Cycle detected
• Continue moving at different speeds until one of the above conditions is met

Code

Finding the middle of a linked list

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

// Find the middle of a linked list with two pointers.
// Time: O(n), Space: O(1)
function middleOfList(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // DECISION FRAMEWORK: Continue until fast pointer reaches the end
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // Including slowPointer in condition helps TypeScript understand both are non-null,
    //  note logically if fasterPointer is not null then slow pointer is not null
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;
    // Move fast pointer 2 steps forward
    fastPointer = fastPointer.next.next;
  }

  // When fast reaches end, slow is at middle
  return slowPointer;
}

// Example usage:
// List: 1 → 2 → 3 → 4 → 5
// When fast is at 5, slow is at 3 (middle)

Detecting if a cycle exists

// Determine if the linked list contains a cycle.
// Time: O(n), Space: O(1)
function hasCycle(head: ListNode | null): boolean {
  let slowPointer = head;
  let fastPointer = head;

  // DECISION FRAMEWORK: Continue until pointers meet or fast reaches end
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // Including slowPointer in condition helps TypeScript understand both are non-null
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;

    // Move fast pointer 2 steps forward
    fastPointer = fastPointer.next.next;

    // Check if pointers met (cycle detected)
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      return true;
    }
  }

  // Fast pointer reached end - no cycle exists
  return false;
}

// Example usage:
// List with cycle: 1 → 2 → 3 → 4 → 5 → 3 (loops back)
// Result: true

Finding the start of a cycle

// Determine if the linked list contains a cycle and
// return the beginning of the cycle, otherwise return null.
// Time: O(n), Space: O(1)
function cycleStart(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // Phase 1: Detect if cycle exists using different speeds
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    slowPointer != null
  ) {
    // TypeScript now knows slowPointer is non-null from loop condition
    slowPointer = slowPointer.next;

    // Move fast pointer 2 steps forward
    fastPointer = fastPointer.next.next;

    // Check if pointers met inside a cycle
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      break; // Cycle detected, proceed to phase 2
    }
  }

  // Check if we exited because no cycle exists
  const fastPointerReachedEnd = fastPointer == null || fastPointer.next == null;
  if (fastPointerReachedEnd) {
    return null;
  }

  // Phase 2: Find the exact start of the cycle
  // Mathematical property: Distance from head to cycle start equals
  // distance from meeting point to cycle start (when moving forward through cycle)
  // - (see below section for more detail of this property)
  //
  // Example with list: 1 → 2 → 3 → 4 → 5 → 6 → 3 (cycle starts at node 3)
  //   - Non-cycle part: 1 → 2 (length = 2)
  //   - Cycle part: 3 → 4 → 5 → 6 → 3 (length = 4)
  //   - Meeting point: Node 5 (when slow and fast first meet)
  //
  //   Distance from head (1) to cycle start (3): 2 steps
  //   Distance from meeting point (5) to cycle start (3): 5→6→3 = 2 steps
  //   These distances are ALWAYS equal!

  // DECISION FRAMEWORK: Reset one pointer to head, move both at same speed
  let pointerAtMeetingPoint = slowPointer;
  let pointerAtHead = head;

  // Continue until both pointers meet at the cycle start
  while (
    pointerAtHead != null &&
    pointerAtMeetingPoint != null &&
    pointerAtMeetingPoint != pointerAtHead
  ) {
    // Move both pointers one step at a time (same speed)
    const nextPositionFromHead = pointerAtHead.next;
    pointerAtHead = nextPositionFromHead;

    const nextPositionFromMeeting = pointerAtMeetingPoint.next;
    pointerAtMeetingPoint = nextPositionFromMeeting;
  }

  // Both pointers now point to the cycle start
  return pointerAtHead;
}

// Example usage:
// List: 1 → 2 → 3 → 4 → 5 → 3 (node 3 is cycle start)
// Result: Node with value 3

Why Phase 2 works: The mathematical proof

The key property: When fast and slow pointers meet inside a cycle, the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (moving forward through the cycle).

Notation

Let's define:

• L = Length of non-cycle part (distance from head to cycle start)
• C = Length of cycle
• k = Distance from cycle start to meeting point (measured along the cycle)

What happens in Phase 1 (detection)

When the pointers meet:

• Slow pointer traveled: L + k steps (L to enter cycle, k more to meeting point)
• Fast pointer traveled: 2(L + k) steps (moves twice as fast)

Since the fast pointer is in a cycle, we can also describe its position as:

• Fast traveled: L + k + nC steps (where n is number of complete loops)

Since both are at the same position:

2(L + k) = L + k + nC
2L + 2k = L + k + nC
L + k = nC
L = nC - k

The critical insight

From L = nC - k, we know:

• L steps from head reaches cycle start
• nC - k steps from meeting point also reaches cycle start

Since we're in a cycle of length C, moving nC - k steps is the same as moving C - k steps (the extra loops don't matter).

From meeting point to cycle start:
- Distance forward through cycle: C - k
- But L = nC - k, and in a cycle, nC - k ≡ C - k (mod C)

Concrete example

List: 1 → 2 → 3 → 4 → 5 → 6 → 3 (cycle starts at node 3)

Setup:
- L = 2 (nodes 1, 2 before cycle)
- C = 4 (cycle: 3 → 4 → 5 → 6 → 3)

Phase 1 - Step-by-step trace until meeting

Step 0 (Start):
  Slow: [1]      Fast: [1]

Step 1:
  Slow: 1 → [2]        Fast: 1 → 2 → [3]

Step 2:
  Slow: 1 → 2 → [3]    Fast: 1 → 2 → 3 → 4 → [5]
  (Slow enters cycle)

Step 3:
  Slow: 1 → 2 → 3 → [4]          Fast: 1 → 2 → 3 → 4 → 5 → 6 → [3]
                                 (Fast completed 1 full loop)

Step 4:
  Slow: 1 → 2 → 3 → 4 → [5]      Fast: 1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → [5]

  ✓ THEY MEET AT NODE 5!

Why node 5?

• Slow took 4 steps to reach node 5
• Fast took 8 steps to reach node 5 (moved twice as fast)
• Once slow entered the cycle at step 2, it took 2 more steps (step 3 and 4) to meet
• Fast was already looping through the cycle, closing the gap by 1 node per step

After meeting at node 5:
- Slow traveled: 4 steps (L=2 to enter cycle, k=2 more to node 5)
- Fast traveled: 8 steps (2 to cycle start, then 6 more = 1.5 loops through cycle)
- k = 2 (distance from cycle start node 3 to meeting point node 5: 3→4→5)
- Verify: L = nC - k → 2 = 1(4) - 2 ✓

Phase 2 - Finding cycle start

Both pointers move at the same speed (1 step at a time):

Reset one pointer to head:
  pointerAtHead: [1]
  pointerAtMeetingPoint: [5]

Step 1:
  pointerAtHead: 1 → [2]
  pointerAtMeetingPoint: 5 → [6]

Step 2:
  pointerAtHead: 1 → 2 → [3]
  pointerAtMeetingPoint: 5 → 6 → [3]

  ✓ BOTH MEET AT NODE 3 (CYCLE START)!

Both pointers traveled exactly L = 2 steps and arrived at the cycle start simultaneously!

Visual proof

List: 1 → 2 → 3 → 4 → 5 → 6 → 3
      |___L___|_____Cycle____|
              ↑           ↑
          start(3)    meet(5)

Distance from head to start: L = 2
Distance from meet to start: (C - k) = (4 - 2) = 2

Since L = nC - k, and we move C - k forward in cycle:
L ≡ C - k (mod C)

Therefore: 2 steps from head = 2 steps from meeting point
Both arrive at cycle start simultaneously!

This mathematical property is what makes Floyd's cycle detection algorithm so elegant - Phase 2 is guaranteed to work because of this distance equality.

Doubt buster

Common doubt: "Why does moving at different speeds guarantee the pointers will meet in a cycle? What if the fast pointer just keeps jumping over the slow pointer?"

This is a sophisticated concern about Floyd's Cycle Detection algorithm. Let's address it with concrete reasoning.

Why you might think the fast pointer could miss the slow pointer

Consider a cycle in a linked list. You might think:

• "The fast pointer moves 2 steps at a time, the slow pointer moves 1 step"
• "In a cycle, couldn't the fast pointer jump right over the slow pointer without ever landing on the same node?"
• "The algorithm seems to assume they'll meet, but is that actually guaranteed?"

Why this thinking is wrong

Key realization: In each iteration, the gap between the fast and slow pointers closes by exactly 1 node!

Let's understand this with the concept of relative speed:

When both pointers are in the cycle:
- Fast pointer moves: 2 nodes per iteration
- Slow pointer moves: 1 node per iteration
- Relative speed (fast catching up to slow): 2 - 1 = 1 node per iteration

This means the distance between them DECREASES by exactly 1 node each iteration.

Concrete example: The gap always closes

Let's trace through a cycle with 5 nodes, where slow is at position 0 and fast is at position 3:

Iteration 0:
Cycle: [0] → [1] → [2] → [3] → [4] → [0] (loops)
        ↑           ↑
       slow        fast
Gap: 3 nodes ahead

Iteration 1:
       [0] → [1] → [2] → [3] → [4] → [0]
              ↑                  ↑
            slow               fast
Gap: 2 nodes ahead (closed by 1)

Iteration 2:
       [0] → [1] → [2] → [3] → [4] → [0]
                     ↑    ↑
                   slow  fast
Gap: 1 node ahead (closed by 1)

Iteration 3:
       [0] → [1] → [2] → [3] → [4] → [0]
                          ↑
                      slow & fast MEET!
Gap: 0 nodes (closed by 1)

The magic: No matter the initial gap size, decreasing by 1 each iteration means they must meet when the gap reaches 0!

Mathematical proof of guaranteed meeting

In a cycle of length C:

• Initial gap between pointers: some distance D (where 0 < D < C)
• Each iteration reduces gap by: 1 node
• Iterations until meeting: D iterations

Why the fast pointer can't "skip over" the slow pointer:

If at iteration N the gap is 2 nodes:

• After N+1 iterations, gap becomes 1 node
• After N+2 iterations, gap becomes 0 nodes → MEETING

There's no way to go from gap=2 to gap=0 in one iteration, because the relative speed is always 1 node per iteration.

Why this works even with different cycle positions

Case 1: Both pointers start in the cycle

• Gap closes by 1 each iteration → guaranteed meeting

Case 2: Pointers enter cycle at different times

• Once both are in the cycle, revert to Case 1
• The fast pointer enters first, then waits for slow pointer
• When slow enters, gap closes by 1 each iteration → guaranteed meeting

The brilliance of Floyd's algorithm

The algorithm leverages three key properties:

1. Constant relative speed: Always 1 node per iteration
2. Circular structure: Gap wraps around, can't escape
3. Inevitable convergence: Gap of D takes exactly D iterations to close to 0

This combination guarantees meeting inside any cycle, making the algorithm both elegant and certain!

Another common doubt

Common doubt: "What if the cycle is extremely large - like a billion nodes? Won't the pointers need to loop around billions of times before meeting, making this algorithm impractically slow?"

This is a legitimate performance concern about Floyd's algorithm. Let's examine why this fear is unfounded.

Why you might worry about massive cycles

Consider a huge linked list with a cycle. You might think:

• "If the cycle has 1 billion nodes, and the pointers need to chase each other around the cycle"
• "The fast pointer might lap the slow pointer many times before they finally meet"
• "This could take billions of iterations, making O(n) time complexity meaningless in practice"

Why this worry is unnecessary

Key realization: The pointers meet within at most one complete traversal of the cycle, regardless of cycle size!

Here's the critical insight: Once both pointers are inside the cycle, they will meet before the slow pointer completes even one full loop of the cycle.

Concrete example: Maximum iterations needed

Let's prove this with worst-case analysis:

Given:
- Cycle length: C nodes
- Slow pointer position in cycle: 0
- Fast pointer position in cycle: 1 (just one node ahead - worst case)

Iteration tracking:
Gap starts at: C - 1 nodes (maximum possible gap in a cycle)
Gap closes by: 1 node per iteration
Iterations to meet: C - 1 iterations

Result: They meet in less than C iterations (less than one full cycle)

Real example with a "huge" cycle

Let's trace a cycle with 10 nodes (representing a billion-node cycle):

Worst case scenario:
- Cycle length: 10 nodes
- Slow at position 0, Fast at position 1
- Maximum gap: 9 nodes

Iteration 0: Slow=0, Fast=1, Gap=9
Iteration 1: Slow=1, Fast=3, Gap=8
Iteration 2: Slow=2, Fast=5, Gap=7
Iteration 3: Slow=3, Fast=7, Gap=6
Iteration 4: Slow=4, Fast=9, Gap=5
Iteration 5: Slow=5, Fast=1, Gap=4  (fast wrapped around)
Iteration 6: Slow=6, Fast=3, Gap=3
Iteration 7: Slow=7, Fast=5, Gap=2
Iteration 8: Slow=8, Fast=7, Gap=1
Iteration 9: Slow=9, Fast=9, MEET!

Total iterations: 9 (which is C-1, where C=10)

Even in the absolute worst case, they met in just 9 iterations for a 10-node cycle!

Time complexity guarantee

For a linked list with n total nodes:

• Non-cycle part: Length L nodes
• Cycle part: Length C nodes
• Total: n = L + C nodes

Phase 1 (reaching the cycle):

• Slow pointer needs L steps to enter cycle
• Fast pointer needs at most L steps
• Iterations: L

Phase 2 (meeting in cycle):

• Maximum gap when slow enters: C - 1 nodes
• Gap closes by 1 per iteration
• Iterations: at most C - 1

Total iterations: L + (C - 1) < L + C = n

This proves the algorithm is strictly O(n) - even with a billion-node cycle, you'll traverse it at most once!

Why this is better than using a hash set

Compare to the naive approach of tracking visited nodes:

Hash Set Approach:
- Time: O(n)
- Space: O(n) - store every visited node

Fast & Slow Pointers:
- Time: O(n)
- Space: O(1) - only two pointers

For 1 billion nodes:
- Hash set needs ~8-16GB of memory
- Fast & Slow needs ~16 bytes (two pointers)

The mathematical beauty

The worst-case scenario is actually bounded by a beautiful property:

Maximum iterations = n - 1

Where n is the total number of nodes. This means:

• 100 nodes → max 99 iterations
• 1,000 nodes → max 999 iterations
• 1,000,000,000 nodes → max 999,999,999 iterations

You never "loop around endlessly" - the algorithm has a hard upper bound that scales linearly with the input size, making it extremely efficient even for massive cycles!