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).

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)).

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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

1. Cycle detection: slow = fast = head; loop while fast and fast.Next exist; advance slow once, fast twice; if they meet, cycle exists.
2. Cycle entry: after meeting, set one pointer to head; move both one step until they meet; that node is the entry.
3. Middle node: slow/fast with fast advancing twice; when fast finishes, slow is middle (document chosen convention for even length).
4. 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.

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.