Pattern #2 — Fast & Slow Pointer 🐢🐇

Pattern #2 — Fast & Slow Pointer 🐢🐇

This one has a fun nickname: "the tortoise and the hare." It's two pointers again — but now one moves faster than the other, and that speed difference is the whole trick.

1. The Idea (in one line)

Two pointers move through a list at different speeds — slow moves 1 step, fast moves 2 steps.

   Real-life analogy 🏃
   ────────────────────
   Two runners on a circular track. One runs twice as fast.
   If the track is a LOOP, the fast runner will eventually
   lap the slow one and they'll MEET. If the track is straight
   (no loop), the fast runner just reaches the end.

   → That's exactly how we detect a cycle in a linked list!

2. The Picture

   NO CYCLE (straight list): fast reaches the end → no meeting
   ───────────────────────────────────────────────────────────
   1 → 2 → 3 → 4 → 5 → null
   S   F
       (fast runs to null, done)


   HAS A CYCLE: fast catches up to slow → they MEET
   ───────────────────────────────────────────────────────────
   1 → 2 → 3 → 4
           ↑    ↓
           7 ← 6 ← 5      ← the list loops back!

   slow moves 1, fast moves 2... eventually
   they land on the SAME node. 🎯 Cycle detected!

3. 🔍 How to SPOT This Pattern

   Use Fast & Slow when you see:
   ✅ "Linked list" + "is there a cycle?"
   ✅ "Find the MIDDLE of a linked list"
   ✅ "Find where the cycle starts"
   ✅ "Happy number" (a number cycle problem)
   ✅ Anything where you'd otherwise use extra memory to
      remember visited nodes → this does it in O(1) space!

4. Worked Example — Find the Middle of a Linked List

   1 → 2 → 3 → 4 → 5

   Start: slow=1, fast=1
   Step 1: slow=2, fast=3
   Step 2: slow=3, fast=5
   fast is at the end → STOP.

   👉 slow is now at 3 — the MIDDLE! ✅

   Why it works: when fast has gone the FULL distance,
   slow has gone HALF the distance. Simple and elegant.

5. The Code Templates 📝

   // A) Detect a cycle
   function hasCycle(head) {
     let slow = head, fast = head;
     while (fast && fast.next) {
       slow = slow.next;          // 1 step
       fast = fast.next.next;     // 2 steps
       if (slow === fast) return true;   // they met → cycle!
     }
     return false;                // fast hit the end → no cycle
   }

   // B) Find the middle
   function findMiddle(head) {
     let slow = head, fast = head;
     while (fast && fast.next) {
       slow = slow.next;
       fast = fast.next.next;
     }
     return slow;                 // slow stops at the middle
   }

6. Practice Problems

   ⭐ Easy
   • Middle of a Linked List
   • Linked List Cycle (yes/no)
   • Happy Number

   ⭐⭐ Medium
   • Linked List Cycle II (find where the cycle starts)
   • Palindrome Linked List (find middle, reverse, compare)
   • Reorder List

7. ⚠️ Common Mistake

   ❌ Forgetting to check BOTH `fast` AND `fast.next` before
      moving. If you skip that check, `fast.next.next` crashes
      when fast is at the last node.

   ✅ Always:  while (fast && fast.next) { ... }

Key Takeaway

   Fast & Slow = two pointers at different speeds. The gap
   between them reveals cycles and midpoints — using ZERO
   extra memory. The go-to for linked-list cycle/middle problems.

Next: Pattern #3 — Sliding Window, the king of subarray/substring problems. 🪟