Fast & Slow Pointers — The Complete Guide

function hasCycle(head: ListNode | null): boolean {
  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;
}
// When to use: "does this linked list have a cycle?"
// Also works for number sequences: next = f(current)
// Key: check fast AND fast.next before advancing

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

  // Phase 1: Detect cycle (find meeting point)
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      // Phase 2: Find cycle start
      let entry = head;
      while (entry !== slow) {
        entry = entry!.next;
        slow = slow!.next;
      }
      return entry; // cycle start node
    }
  }

  return null; // no cycle
}
// Why does Phase 2 work?
// Let D = distance from head to cycle start
// Let K = distance from cycle start to meeting point
// At meeting: slow traveled D + K, fast traveled D + K + nC
// Since fast = 2 × slow: D + K + nC = 2(D + K) → D = nC - K
// So moving D steps from head AND from meeting point both reach cycle start.

// When to use: "find where the cycle begins",
// "find the duplicate number" (array as linked list)

// Returns the FIRST middle (for even-length lists)
function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

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

  return slow;
}

// Returns the SECOND middle (for even-length lists)
function middleNodeSecond(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;

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

  return slow;
}
// 1 → 2 → 3 → 4 → 5:       both return node 3 (odd length)
// 1 → 2 → 3 → 4 → 5 → 6:   first returns 3, second returns 4
//
// When to use: "find the middle", "split list in half",
// prerequisite for palindrome check and reorder list

function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;

  // Step 1: Find middle (slow ends at first middle)
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next && fast?.next?.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // Step 2: Reverse second half
  let prev: ListNode | null = null;
  let curr = slow!.next;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Step 3: Compare first half and reversed second half
  let left = head;
  let right = prev;
  while (right) {
    if (left!.val !== right.val) return false;
    left = left!.next;
    right = right.next;
  }

  return true;
}
// Time: O(n) — three passes (find middle, reverse, compare)
// Space: O(1) — only pointer manipulation
// When to use: "is this linked list a palindrome?" with O(1) space

function isHappy(n: number): boolean {
  function getNext(num: number): number {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }

  let slow = n;
  let fast = getNext(n);

  while (fast !== 1 && slow !== fast) {
    slow = getNext(slow);           // 1 step
    fast = getNext(getNext(fast));   // 2 steps
  }

  return fast === 1;
}
// If the sequence reaches 1, fast gets there first → return true.
// If the sequence cycles, slow and fast meet → return false.
// Key insight: any bounded sequence that doesn't terminate must cycle.
// Digit square sums are bounded (e.g., 999 → 243), so it must cycle or reach 1.

function findDuplicate(nums: number[]): number {
  // Treat array as linked list: index → nums[index]
  // A duplicate means two indices map to the same value → cycle

  // Phase 1: Detect cycle (find meeting point)
  let slow = nums[0];
  let fast = nums[0];

  do {
    slow = nums[slow];           // 1 step
    fast = nums[nums[fast]];     // 2 steps
  } while (slow !== fast);

  // Phase 2: Find cycle start (= the duplicate value)
  let entry = nums[0];
  while (entry !== slow) {
    entry = nums[entry];
    slow = nums[slow];
  }

  return entry;
}
// Time: O(n) — Floyd's algorithm
// Space: O(1) — no extra data structures
// Why it works: the duplicate value is the entry point of the cycle.
// Two different indices point to it → it's where paths converge.

function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;

  // Step 1: Find middle
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next && fast?.next?.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // Step 2: Reverse second half
  let prev: ListNode | null = null;
  let curr = slow!.next;
  slow!.next = null; // cut the list
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Step 3: Interleave (merge alternating)
  let first = head;
  let second = prev;
  while (second) {
    const tmp1 = first!.next;
    const tmp2 = second.next;
    first!.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}
// Time: O(n) — three linear passes
// Space: O(1) — only pointer manipulation
// This is the "composite pattern" — find middle + reverse + merge.
// Many linked list problems decompose into these three building blocks.

List: 1 → 2 → 3 → 4 → 5 → 3 (cycle back to node 3)

Positions (node values):
Step 0: slow=1, fast=1                    (start)
Step 1: slow=2, fast=3                    (slow +1, fast +2)
Step 2: slow=3, fast=5                    (slow +1, fast +2)
Step 3: slow=4, fast=4                    (slow +1, fast +2 → 3→4)
        slow === fast → CYCLE DETECTED ✓

Why they met at node 4:
- After entering the cycle, fast gains 1 position per step on slow
- Cycle length = 3 (nodes 3, 4, 5)
- Fast was 2 ahead of slow in the cycle → met after 1 more step
- They ALWAYS meet within one full cycle length

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

D = distance from head to cycle start = 2 (nodes 1, 2)
C = cycle length = 3 (nodes 3, 4, 5)

Phase 1: Find meeting point
  slow traveled: D + K = 2 + 1 = 3 steps (at node 4)
  fast traveled: 2(D + K) = 6 steps (also at node 4)
  K = distance from cycle start to meeting point = 1

Phase 2: Find cycle start
  Reset entry pointer to head (node 1)
  Keep slow at meeting point (node 4)
  
  Step 1: entry=2, slow=5     (both move +1)
  Step 2: entry=3, slow=3     (both move +1)
  entry === slow → CYCLE START = node 3 ✓

Why Phase 2 works:
  D = nC - K  (from the math: fast = 2 × slow)
  So D steps from head = D steps from meeting point
  Both land on the cycle start.
  
  In our example: D=2, C=3, K=1 → D = 3-1 = 2 ✓

Odd length: 1 → 2 → 3 → 4 → 5

Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
fast.next is null → STOP
Middle = slow = node 3 ✓ (exact middle)

Even length: 1 → 2 → 3 → 4 → 5 → 6

"Second middle" version (while fast && fast.next):
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=null (fast was 5, fast.next=6, fast.next.next=null)
Wait — fast=5, fast.next=6, so we continue:
Step 3: slow=4, fast=null (6.next = null, so fast becomes null)
Middle = slow = node 4 ✓ (second of two middles)

"First middle" version (while fast.next && fast.next.next):
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
fast.next=6, fast.next.next=null → STOP
Middle = slow = node 3 ✓ (first of two middles)

Key: The loop condition determines which middle you get for even-length lists.

Does the problem involve a linked list or a sequence with "next" semantics?
├── NO  → Fast-slow probably doesn't apply.
│         Consider Two Pointers, Sliding Window, or Hashing.
└── YES → Do you need to detect a cycle?
          ├── YES → Is O(1) space required?
          │         ├── YES → Floyd's Cycle Detection (Template 1)
          │         └── NO  → Hash Set is simpler (but O(n) space)
          └── NO  → Do you need the cycle START?
                    ├── YES → Floyd's Phase 1 + Phase 2 (Template 2)
                    └── NO  → Do you need the MIDDLE of the list?
                              ├── YES → Fast-Slow Find Middle (Template 3)
                              └── NO  → Do you need palindrome check / reorder?
                                        ├── YES → Composite: middle + reverse + merge (Template 4)
                                        └── NO  → Do you need Kth from end?
                                                  ├── YES → Fixed-gap two pointers (advance fast K first)
                                                  └── NO  → Consider other linked list techniques