Fast & Slow Pointers (Cycle Detection · Midpoints · Floyd's Cycle-Finding)

Core Concept of Fast & Slow Pointers

• Fast Pointer (fast): Moves 2 steps at a time.
• Slow Pointer (slow): Moves 1 step at a time.
• Logic: If a cycle exists, the fast pointer will eventually "lap" and meet the slow pointer. Otherwise, the fast pointer will reach the end of the list first.

Middle of the Linked List (LeetCode 876)

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // Odd length: Exactly the middle; Even length: First node of the second half
}

Reasoning: Let the list length be $n$. When the loop finishes, fast has traveled $2k$ steps and slow has traveled $k$ steps. When fast reaches the end ($2k = n$), slow is exactly at $n/2$.

Odd/Even Consistency:

n=5: 1 → 2 → 3 → 4 → 5 → null
fast: 1 → 3 → 5 → null; slow: 1 → 2 → 3  → Returns 3 (Middle) ✓

n=6: 1 → 2 → 3 → 4 → 5 → 6 → null
fast: 1 → 3 → 5 → null (via fast.next=6); slow: 1 → 2 → 3 → 4 → Returns 4 (Start of 2nd half) ✓

Common Use: Splitting a linked list for Merge Sort.

Linked List Cycle (LeetCode 141)

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; // Meeting point found, a cycle exists
    }
    return false; // Fast reached the end, no cycle
}

Why Differentiated Speeds Work: Once both pointers are in the cycle, the relative distance between them changes by 1 each step. Thus, the faster pointer will eventually catch up to the slower one within one full loop of the cycle.

Linked List Cycle II: Finding the Cycle Entrance (LeetCode 142)

This is the most elegant application of Floyd's Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm):

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // Phase 1: Detect if a cycle exists and find a meeting point
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null; // No cycle

    // Phase 2: Find the entrance
    // Move slow back to head, leave fast at the meeting point
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next; // Both move 1 step at a time
    }
    return slow; // Intersection is the cycle entrance
}

Mathematical Proof:

head ──────────── Entrance ──────── Meeting Point
    <---- a -----> <--- b --->
                   <--- c ----> (Remaining circle length, b+c = cycle length)

At meeting point:
    Step distance (slow) = a + b
    Step distance (fast) = a + b + n(b + c) (wrapped 'n' times)
Since fast = 2 * slow:
    a + b + n(b + c) = 2(a + b)
    a = n(b + c) - b = (n - 1)(b + c) + c
When n=1:
    a = c

Conclusion: The distance from the head to the entrance (a) is equal to the distance from the meeting point to the entrance (c) plus zero or more full cycle lengths.

Remove N-th Node From End of List (LeetCode 19)

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;

    // Fast pointer moves n+1 steps ahead first
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // Both pointers move together until fast reaches null
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // 'slow' now points to the PREDECESSOR of the target node
    slow.next = slow.next.next;
    return dummy.next;
}

Why the Dummy node? To handle the edge case where the head itself needs to be removed ($n = \text{length}$).
Why $n+1$ steps? To position slow precisely at the node right before the one we want to delete.

Palindrome Linked List (LeetCode 234)

Merging Midpoint Detection + Reversing + Comparison:

boolean isPalindrome(ListNode head) {
    // 1. Find midpoint (slow)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. Reverse second half
    ListNode prev = null, cur = slow;
    while (cur != null) {
        ListNode nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    
    // 3. Comparison
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

Complexity: O(n) time, O(1) space (manipulating nodes in-place).

Reorder List (LeetCode 143)

Transforming $L_0 \rightarrow L_1 \rightarrow \dots \rightarrow L_n$ into $L_0 \rightarrow L_n \rightarrow L_1 \rightarrow L_{n-1} \rightarrow \dots$.

void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    
    // 1. Find midpoint
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. Reverse second half and disconnect the two halves
    ListNode secondHalf = reverse(slow.next);
    slow.next = null;

    // 3. Interweave the two lists
    ListNode first = head, second = secondHalf;
    while (second != null) {
        ListNode tmp1 = first.next;
        ListNode tmp2 = second.next;
        
        first.next = second;
        second.next = tmp1;
        
        first = tmp1;
        second = tmp2;
    }
}

private ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    return prev;
}

Comparison Summary

Fast & Slow Pointers in Arrays

Beyond linked lists, this technique handles "in-place filtering" or cycle detection mapping in arrays:

// Find Duplicate Number (LeetCode 287)
// Treat nums as a linked list where i → nums[i]. A duplicate value creates a cycle.
int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    // Find meeting point
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    
    // Find cycle entrance
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Highlights: Space O(1), Time O(n), without modifying the input array—an elegant repurposing of Floyd’s algorithm.