Algorithms from zero

Fast and slow pointers

Crux Use two pointers advancing at different speeds to find the middle of a list, detect cycles (Floyd''''s tortoise-and-hare), and prove that the pointers must meet inside any cycle. A technique that solves hard linked-list problems with O(1) space.

◷ 24 min

Last lesson you reversed a linked list by updating pointers one by one. Today you will learn a different pointer trick: send two pointers down the list at different speeds. The slow pointer moves one step; the fast pointer moves two. If the list has a cycle, the pointers will meet. If the list is linear (no cycle), the fast pointer falls off the end. This technique—called the tortoise-and-hare method—can find the middle node and detect cycles with only O(1) extra space.

Goal

After this lesson you can find the middle node of a linked list using two pointers, detect whether a linked list contains a cycle, explain why fast and slow pointers must meet inside a cycle, apply the technique to hard linked-list problems, and recognize when two pointers at different speeds is the right approach.

The idea

The core idea: two pointers at different speeds

Imagine walking down a path with a friend. You walk one step per second; your friend walks two steps per second. If the path is linear (has an end), your friend reaches the end while you are still in the middle. If the path loops back on itself, your friend will lap you—eventually your friend catches up and you meet again.

In a linked list, we use two pointers (slow and fast) to model this:

Slow pointer: Moves one step per iteration (to the next node).
Fast pointer: Moves two steps per iteration (skips one node, goes two ahead).

slow: 1 step
fast: 2 steps

Finding the middle node

Given a list [10] → [20] → [30] → [40] → [50], what is the middle?

Use two pointers, both starting at the head. On each iteration:

Move slow one step.
Move fast two steps.
When fast reaches the end, slow is at the middle.

Start: slow = 10, fast = 10
After 1: slow = 20, fast = 30
After 2: slow = 30, fast = 50

Loop exits because fast.next is null.
slow is at 30, the middle.

The insight: When fast reaches the end, slow has taken half as many steps and is at the middle.

Detecting a cycle: the tortoise-and-hare algorithm

A cycle means the list eventually loops back to an earlier node. Example: [10] → [20] → [30] → [20] (the pointer of 30 points back to 20, creating a cycle).

Using two pointers at different speeds, if there is a cycle:

Slow moves one step per iteration.
Fast moves two steps per iteration.
If fast ever reaches null, there is no cycle.
If fast and slow ever point to the same node, there is a cycle.

Why must they meet? In a cycle, the fast pointer gains on the slow pointer by one step each iteration (it moves two while slow moves one). Eventually, fast laps slow.

Cycle example: [1] → [2] → [3] → [4] → [5] → [3] (loops back to 3)

Start: slow = 1, fast = 1
Iter 1: slow = 2, fast = 3
Iter 2: slow = 3, fast = 5
Iter 3: slow = 4, fast = 4 (fast caught slow! Cycle detected.)

Why they must meet inside the cycle

Suppose the cycle has length c (the number of nodes in the loop). When slow enters the cycle:

Fast is ahead and moving twice as fast.
Each iteration, fast gains one step on slow (moves 2, slow moves 1).
The gap between them decreases by 1 each step.
Eventually the gap becomes 0, and they meet.

The key fact: They meet somewhere inside the cycle, never outside it. This is because once slow enters the cycle, it will never leave; fast is always ahead, so it is already inside. Eventually fast catches slow.

Important caveat: This detects the cycle exists, but does not say where it starts.

To find the cycle start (the first node of the loop), you need a second pass:

After detecting the cycle, place one pointer at the head.
Place the other pointer where slow and fast met.
Move both at speed 1 (one step each iteration).
They meet at the cycle start.

(We will not code this in detail—it is a follow-up technique—but it is important to know the limitation.)

The code

Finding the middle node:

function findMiddle(head) {
  let slow = head;
  let fast = head;
  
  // Move fast two steps, slow one step, until fast reaches the end
  while (fast !== null && fast.next !== null) {
    slow = slow.next;         // Move slow one step
    fast = fast.next.next;    // Move fast two steps
  }
  
  return slow;  // slow is at the middle
}

Detecting a cycle (tortoise-and-hare):

function hasCycle(head) {
  if (head === null || head.next === null) return false;
  
  let slow = head;
  let fast = head;
  
  // If there is a cycle, fast will eventually catch slow
  while (fast !== null && fast.next !== null) {
    slow = slow.next;         // Move slow one step
    fast = fast.next.next;    // Move fast two steps
    
    if (slow === fast) {
      return true;  // Cycle detected
    }
  }
  
  return false;  // fast reached the end; no cycle
}

Try both algorithms interactively:

class Node {
constructor(value, next = null) {
  this.value = value;
  this.next = next;
}
}

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

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

return slow;
}

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

let slow = head;
let fast = head;

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

return false;
}

// Test 1: Find middle of [10, 20, 30, 40, 50]
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);

const middle = findMiddle(head);
console.log("Middle of [10, 20, 30, 40, 50] is:", middle.value);

// Test 2: No cycle
console.log("Cycle in [10, 20, 30, 40, 50]?", hasCycle(head));

// Test 3: Cycle — make node 50 point back to node 30
const node30 = head.next.next;
head.next.next.next.next.next = node30;  // 50 → 30

console.log("Cycle after creating loop?", hasCycle(head));

Output

Step-by-step trace

Let us trace finding the middle of [10] → [20] → [30] → [40] → [50] using two pointers.


      1
      let slow = head;
    

      2
      let fast = head;
    

      3
      while (fast !== null && fast.next !== null) {
    

      4
        slow = slow.next;
    

      5
        fast = fast.next.next;
    

      6
      }

Now trace cycle detection: [1] → [2] → [3] → [4] → [3] (cycle back to 3).


      1
      let slow = head;
    

      2
      let fast = head;
    

      3
      while (fast !== null && fast.next !== null) {
    

      4
        slow = slow.next;
    

      5
        fast = fast.next.next;
    

      6
        if (slow === fast) return true;
    

      7
      }

Complexity

Fast and slow pointers:

Operation	Time	Space
Find middle of a list	O(n)	O(1)
Detect cycle (tortoise-and-hare)	O(n)	O(1)
Find cycle start	O(n)	O(1)

Why O(n) for all? We visit each node in the list once (or until we detect a cycle). The fast pointer reaches the end faster, but we still iterate through the list structure.

Why O(1) space? We only use two pointers—constant space, no hash set, no array.

Compare to naive cycle detection: Using a hash set to store visited nodes also finds cycles in O(n) time but costs O(n) space. Two pointers achieve the same in O(1) space.

Practice 0 / 5

In the list [10] → [20] → [30] → [40] → [50], what node is the middle?

Using the fast-and-slow-pointer technique to find the middle, when should you stop?

A linked list is [1] → [2] → [3] → [4] → [3] (node 4's next points back to 3). What does the tortoise-and-hare algorithm return?

Why must the fast and slow pointers eventually meet if there is a cycle?

A list has no cycle: [10] → [20] → [30] → [40] → null. What does hasCycle return?

Edge cases

Even vs. odd length lists: For a list of even length [10, 20, 30, 40], the middle is ambiguous (is it 20 or 30?). Most implementations return the second middle (30) because when fast falls off the end, slow is at position length/2 + 1. Be aware of this when using the middle-finding technique.

Common mistake

“Fast pointer should move by 3 or 4 steps to go faster.” No. Fast must move by exactly 2 steps. Why? If fast moves by k > 2 steps, it might skip over the slow pointer and never catch it, even if there is a cycle. The 2-step rule guarantees convergence in a cycle.

More practice

Common follow-up: Given a list with a cycle, find the first node of the cycle (where the loop starts). Hint: After detecting the cycle with slow and fast, place one pointer at the head and the other where they met. Move both one step at a time. They meet at the cycle start. This requires mathematical proof (related to the cycle length and position where they meet), but the algorithm is elegant.

Check yourself

Quiz

Why is the two-pointer (fast-and-slow) technique for cycle detection better than using a hash set of visited nodes?

Recap

Fast and slow pointers (tortoise-and-hare):

Core idea: Use two pointers advancing at different speeds (slow: 1 step, fast: 2 steps).
Finding the middle: Move both pointers until fast reaches the end. Slow is at the middle (or the second middle for even-length lists).
Detecting cycles: In a list with a cycle, fast will eventually lap slow. If they ever point to the same node, a cycle exists.
Why they meet in a cycle: Fast gains 1 step on slow each iteration. In a finite cycle, the gap shrinks until it reaches 0.
Space advantage: O(1) extra space vs. O(n) for a hash set, both in O(n) time.
Fast must move by 2, not 3 or 4: Only 2 steps guarantees convergence in a cycle.
Caveat: This detects cycles but does not directly identify where the cycle starts. A second pass is required for that.

Next, you will learn stacks and queues—two data structures built on lists that enforce rules about how and when you can add and remove elements. These tools are essential for parsing, undo/redo, and breadth-first search.

Continue the climb ↑The stack