03. Fast & Slow Pointers

TL;DR

Two pointers traverse a linked list (or array-as-graph) at different speeds—typically one step vs two steps per move—so that meeting reveals periodic structure: cycle existence, cycle entry, or the middle of a sequence. The same tortoise and hare idea maps index (index \to nums[index]) to detect cycles in a functional graph (duplicate-finding).

Core Basics

Object: two speeds on a linked structure; cycle detection, middle finding, or in-place reversal prep.
Math fact: if a cycle exists, slow/fast must meet inside the loop when fast moves 2× per step.
Staff-level bar: connect pointer steps to implicit graph or modular arithmetic on list length for follow-ups.

Recognition Cues

Phrases: "cycle in linked list", "find duplicate", "middle of linked list", "return node where cycle begins", "nums.length == n+1, values in 1..n".
Shapes: singly linked list; array interpreted as edges (index \to nums[index]); Floyd often applies when space must be (O(1)).

Use-case Lens

Best when: a structure behaves like a path through next links and you need cycle/middle/entry information with (O(1)) extra space.
Not for: arbitrary graph traversal with branching neighbors; use BFS/DFS and visited state.
Main invariant: fast moves faster than slow, so a cycle forces a meeting; acyclic paths end at nil/out-of-bounds.
Interview move: after detecting a meeting, explain the second phase separately: reset one pointer to head and move both one step to find cycle entry.

Diagram

Loading diagram…

Step-by-step Visual

Example: linked list cycle A -> B -> C -> D -> B.

Loading diagram…

The meeting point only proves a cycle. To find the entry, reset one pointer to head; move both one step at a time until they meet at the cycle start.

Understanding

If a linked list has a cycle, the fast pointer eventually laps the slow pointer inside the cycle. After meeting, resetting one pointer to head and advancing both one step at a time aligns them at the cycle entry—equalizes distances along the mathematical relation between tail length and cycle length. For middle detection, when fast reaches the end, slow sits at the midpoint for odd length and the first middle for even length under common conventions.

Generic Recipe

Cycle detection: slow = fast = head; loop while fast and fast.Next exist; advance slow once, fast twice; if they meet, cycle exists.
Cycle entry: after meeting, set one pointer to head; move both one step until they meet; that node is the entry.
Middle node: slow/fast with fast advancing twice; when fast finishes, slow is middle (document chosen convention for even length).
Duplicate on indices: treat nums as next(index) = nums[index]; Floyd finds cycle; meeting point analysis yields duplicate (or use entry-step variant depending on problem setup).

Complexity

Time: (O(n)) for list length (n); at most two passes for cycle entry.
Space: (O(1)) pointers only—main reason to prefer Floyd over hash sets.

Memory Hooks

Operational mantra: run two speeds over the same path; meeting, gap, or midpoint tells you the hidden structure.
Anti-panic: convert the structure to "two speeds on one path"; meeting proves a cycle, and reset-to-head finds entry.

Study Pattern (SDE3+)

Recognition drill (10 min): distinguish cycle detection, middle finding, kth-from-end, and index-as-linked-list problems.
Implementation sprint (25 min): code cycle existence and cycle entry without extra memory; narrate the reset proof.
Staff follow-up (10 min): discuss read-only arrays, malformed lists, and what breaks under concurrent mutation.

Generic Code Template

Go

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

func detectCycleEntry(head *ListNode) *ListNode {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			slow = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow
		}
	}
	return nil
}

func middleNode(head *ListNode) *ListNode {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func main() {}

JavaScript

// Cycle detection (LeetCode-style ListNode: { val, next }).
function hasCycle(head) {
  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;
}

// Cycle entry: returns node or null.
function detectCycle(head) {
  let slow = head;
  let fast = 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;
}

// Middle of list (second middle when even length, common choice).
function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Variants

Existence — boolean cycle test before spending time on length or reversal.
Entry node — phase-two pointer from head with step-one walk for both.
Middle / split — palindrome list: middle, reverse second half, compare; reorder list: find mid, reverse, interleave.
Duplicate number (indices) — implicit graph Floyd; alternative mathematical derivations exist but cycle framing matches fast/slow mental model.

Representative Problems

141. Linked List Cycle — cycle existence
142. Linked List Cycle II — cycle entry
287. Find the Duplicate Number — Floyd on index graph
234. Palindrome Linked List — middle + compare halves

Anti-patterns

Using fast.Next.Next without checking fast.Next first—null dereference risk.
Wrong cycle-entry reset—must advance both one step after repositioning one pointer to head.
Assuming middle convention—clarify first vs second middle for even-length lists in interview.
Hash-set cycle detection when (O(1)) space is required—Floyd is the standard substitute.

On this page