Pattern 04: Fast & Slow Pointers (Floyd's Cycle Detection)

0. The Template (Copy-Paste Skeleton)

One skeleton, three questions: is there a cycle, where does it start, what’s the middle.

// TEMPLATE A — CYCLE DETECTION (Floyd's tortoise & hare)
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {   // BOTH checks — fast moves 2 steps
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;            // they meet ⇒ cycle
    }
    return false;                                 // fast hit null ⇒ no cycle
}

// TEMPLATE B — FIND THE CYCLE'S ENTRY NODE (LC 142)
ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {                       // PHASE 2: reset one pointer to head
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }  // both move 1 step
            return p;                             // meeting point == cycle entry
        }
    }
    return null;
}

// TEMPLATE C — MIDDLE OF THE LIST
ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    return slow;   // even length → SECOND middle. Want the FIRST? start fast at head.next
}

// TEMPLATE D — SAME IDEA ON NUMBERS (Happy Number, LC 202)
int slow = n, fast = n;
do { slow = next(slow); fast = next(next(fast)); } while (slow != fast);
return slow == 1;

Why Phase 2 of Template B works (say this in the interview)

Let a = head→cycle-entry, b = entry→meeting-point, c = rest of the cycle. Fast travelled twice as far: a + b + c + b = 2(a + b) ⇒ c = a. So the distance from the meeting point back to the entry equals the distance from the head to the entry — walk both at speed 1 and they collide exactly at the entry.

Guard-condition rules

• Fast moves 2 → check fast != null && fast.next != null. One check is not enough.
• Fast moves 1 (rare) → fast != null suffices.
• Getting the first of two middles: start fast = head.next.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Detect a cycle in a linked list”
• “Find the middle of a linked list”
• “Find the start of the cycle”
• “Happy Number” (repeated digit-squaring)
• Anything involving a sequence that might loop back on itself

The Algorithm (Pseudocode)

Cycle Detection:

slow = head
fast = head

while (fast != null && fast.next != null):
    slow = slow.next          // 1 step
    fast = fast.next.next     // 2 steps

    if (slow == fast):
        return true  // cycle detected

return false  // no cycle

Find Cycle Start:

// After detecting cycle (slow == fast):
slow = head
while (slow != fast):
    slow = slow.next
    fast = fast.next    // both move 1 step now

return slow  // this is the cycle start

The ‘Trick’ to Know

• Mathematical proof for cycle start: When slow and fast meet, slow has traveled distance d. Fast has traveled 2d. The difference d is a multiple of the cycle length. Resetting slow to head and moving both at speed 1 guarantees they meet at the cycle start.
• Finding middle: When fast reaches the end, slow is at the middle (fast moves 2x speed).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Linked List Cycle - LC 141

Brute Force: HashSet - O(n) time, O(n) space

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();

        ListNode current = head;
        while (current != null) {
            if (!visited.add(current)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

Optimal: Floyd’s Cycle Detection - O(n) time, O(1) space

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;

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

            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

Java Architecture Insights

• Reference comparison (==): We compare node references, not values. Two nodes with the same val are NOT the same node unless they occupy the same memory address.
• Why fast != null && fast.next != null? The order matters. If fast is null, accessing fast.next throws NPE. Short-circuit evaluation (&&) prevents this.
• Why not equals()? ListNode doesn’t override equals(). Default Object.equals() uses == anyway. Using == is clearer about intent (identity, not value equality).

---

3. Mental Model & Visualization

ASCII Diagram (Cycle Detection)

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

Step 0: S=1, F=1
Step 1: S=2, F=3
Step 2: S=3, F=5
Step 3: S=4, F=4  ← MEET! Cycle detected

Finding cycle start:
  Reset slow to head (1), keep fast at 4
  Step A: S=2, F=5
  Step B: S=3, F=3  ← MEET at node 3 = cycle start

Senior Mental Trigger

“Linked list + cycle/middle = tortoise and hare (slow moves 1, fast moves 2).”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 141	Linked List Cycle	Easy
LC 876	Middle of the Linked List	Easy
LC 202	Happy Number	Easy
LC 234	Palindrome Linked List	Easy
LC 83	Remove Duplicates from Sorted List	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 142	Linked List Cycle II (Find Start)	Medium
LC 287	Find the Duplicate Number	Medium
LC 457	Circular Array Loop	Medium
LC 143	Reorder List	Medium
LC 19	Remove Nth Node From End of List	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
HashSet	O(n)	O(n)	Store every visited node
Fast & Slow	O(n)	O(1)	Two pointers, constant space