Fast Slow Pointers | Floyd's Algorithm | Linked List

Overview

The fast and slow pointers technique (also called tortoise and hare or Floyd's algorithm) uses two pointers that move through the linked list at different speeds. Typically the slow pointer moves one step at a time and the fast pointer moves two steps. This simple idea solves several classic problems in O(n) time and O(1) space: cycle detection, finding the middle node, and finding the node where a cycle starts.

Why it works: When fast moves at 2x speed, it covers twice the distance. On a list with a cycle, fast eventually "laps" slow and they meet. On a list without a cycle, fast reaches the end. The relative movement gives you information about the list structure without extra space.

When to Use Fast and Slow Pointers

Cycle detection — Determine if the list has a cycle (a node's next points to an earlier node).
Find the middle node — When fast reaches the end, slow is at the middle (or the first of the two middle nodes in even-length lists).
Palindrome linked list — Find the middle, reverse the second half, then compare.
Reorder list — Find middle, reverse second half, merge alternately.
Find cycle start — After detecting a cycle, use a second phase to find the node where the cycle begins.

How It Works

Initialize: slow = head, fast = head (or both at a dummy if you use one).
In each step: move slow once (slow = slow.next) and fast twice (fast = fast.next?.next or two steps).
Cycle detection: If fast ever meets slow (and neither is null), there is a cycle. If fast reaches null, there is no cycle.
Find middle: When fast reaches the end (or the node before null), slow is at the middle. For even length, slow is usually the first of the two middle nodes if you stop when fast.next === null.
Always check fast and fast.next for null before advancing to avoid null pointer errors.

Example 1: Linked List Cycle (Detection)

Problem: Given the head of a linked list, determine if the list has a cycle.

If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle. If there is no cycle, fast will reach null.

function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

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

Check fast && fast.next so we never call next on null.
Time: O(n), Space: O(1).

Example 2: Find the Middle Node

Problem: Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one. (Common variant: return the first middle for even length.)

When fast reaches the end (or the last node), slow is at the middle. For "second middle" we advance until fast === null; for "first middle" we stop when fast.next === null.

function middleNode(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

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

When the list has even length, this returns the second middle (e.g. in [1,2,3,4], slow ends at 3). To get the first middle (2), stop when fast.next === null (i.e. don't move slow on the last step when fast is at the last node).
Time: O(n), Space: O(1).

Example 3: Find Where the Cycle Starts

Problem: If the list has a cycle, return the node where the cycle begins. Otherwise return null.

Floyd's cycle-finding: After slow and fast meet, reset one pointer to head and move both one step at a time. They meet again at the cycle start.

function detectCycle(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

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

Time: O(n), Space: O(1).

Example 4: Palindrome Linked List (Middle + Reverse)

Problem: Check if a linked list is a palindrome. O(n) time, O(1) space.

Use fast/slow to find the middle, reverse the second half, then compare the first half with the reversed second half.

function isPalindrome(head: ListNode | null): boolean {
  if (head === null || head.next === null) return true;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  let second = reverseList(slow);
  let first: ListNode | null = head;
  while (second !== null) {
    if (first!.val !== second.val) return false;
    first = first!.next;
    second = second.next;
  }
  return true;
}
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Time: O(n), Space: O(1).

Example 5: Reorder List (Middle, Reverse, Merge)

Problem: Reorder list so that nodes alternate: L0 → Ln → L1 → Ln−1 → …

Find the middle with fast/slow, reverse the second half, then merge the first half and the reversed second half alternately.

function reorderList(head: ListNode | null): void {
  if (head === null || head.next === null) return;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next?.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  let second = reverseList(slow!.next);
  slow!.next = null;
  let first: ListNode | null = head;
  while (second !== null) {
    const next1 = first!.next;
    const next2 = second.next;
    first!.next = second;
    second.next = next1;
    first = next1;
    second = next2;
  }
}

Time: O(n), Space: O(1).

Edge Cases

Empty list — Return null or false as appropriate; avoid dereferencing head.
Single node — No cycle; middle is the only node. Handle in cycle detection (fast.next is null) and middle (return head).
Two nodes — Cycle possible (second points to first). Middle is second node if you use "second middle" rule.
Even vs odd length — For "first middle" stop when fast.next === null; for "second middle" stop when fast === null.

Common Mistakes

Not checking fast.next — Before doing fast = fast.next.next, ensure fast.next is not null.
Wrong loop condition — Use while (fast !== null && fast.next !== null) (or equivalent) so you never access null.
Off-by-one for middle — Decide whether you want first or second middle for even length and adjust when you stop.
Modifying the list — In palindrome/reorder you reverse the second half; ensure you don't break the list (e.g. set middle.next = null before reversing).

Time and Space Complexity

Time: O(n) — each pointer touches each node a constant number of times.
Space: O(1) — only two (or a few) pointers.

Summary

Fast and slow pointers move at 1x and 2x speed to detect cycles, find the middle, or derive list structure in O(1) space.
Cycle: If fast meets slow, there is a cycle; use a second phase to find the cycle start.
Middle: When fast reaches the end, slow is at the middle (choose first or second middle by when you stop).
Combine with Reverse In-Place for palindrome and reorder list.

See also Cycle Detection and Find Middle for dedicated guides.

Fast and Slow Pointers (Floyd)