Fast & Slow Pointers (Floyd's Algorithm)

1. Introduction: The Tortoise and the Hare

If two runners are on a straight track, and one runs twice as fast as the other, the fast runner will simply cross the finish line first. But what if the track is a circle? The fast runner will eventually lap the slow runner, passing them from behind!

This intuitive concept is the foundation of Floyd’s Cycle Finding Algorithm, famously known as the Fast and Slow Pointer Pattern (or Tortoise and Hare). It is the most powerful technique for solving Linked List problems involving cycles, finding the middle without knowing the length, or determining structural properties in a single pass.

2. Core Concept: The Differential Speed

In a Linked List, we use two pointers that both start at the head.

1. Slow Pointer (Tortoise): Moves exactly 1 step at a time (slow = slow.next).
2. Fast Pointer (Hare): Moves exactly 2 steps at a time (fast = fast.next.next).

Because the fast pointer moves exactly twice as fast:

• When the fast pointer reaches the end of the list (the finish line), the slow pointer will be exactly at the middle of the list.
• If the list contains a loop (cycle), the fast pointer will get trapped inside it. Eventually, the slow pointer will enter the cycle as well, and the fast pointer will "lap" the slow pointer. If slow == fast at any point, a cycle definitively exists.

3. Beginner Code Example: Middle of the Linked List

Problem Statement: (LeetCode 876) Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

The Naive Approach: Traverse the list to find the total length $N$ ($O(N)$). Divide by 2. Traverse again to index $N/2$ ($O(N)$). The Optimal Approach: Use Fast & Slow pointers to do it in one single pass!

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MiddleNode {
    public static ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        // Fast pointer must check its own validity and its NEXT node's validity
        // to prevent NullPointerException when jumping two steps!
        while (fast != null && fast.next != null) {
            slow = slow.next;         // Move 1 step
            fast = fast.next.next;    // Move 2 steps
        }
        
        // When fast reaches the end, slow is exactly in the middle.
        return slow;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We make one pass. Specifically, we process $N/2$ iterations.
• Space Complexity: $O(1)$. Only two pointers are used.

4. Intermediate Code Example: Linked List Cycle

Problem Statement: (LeetCode 141) Given head, the head of a linked list, determine if the linked list has a cycle in it.

The Hash Set Trap: You could just put every visited node in a HashSet. If set.contains(node) is true, you found a cycle! However, this uses $O(N)$ extra memory. The interviewer explicitly wants an $O(1)$ memory solution.

public class LinkedListCycle {
    public static boolean hasCycle(ListNode head) {
        // Empty list or single node without cycle
        if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            // The pointers have met! A cycle exists.
            if (slow == fast) {
                return true;
            }
        }
        
        // Fast pointer reached the null terminator. No cycle.
        return false;
    }
}

5. Advanced Code Example: Find the Starting Node of the Cycle

Problem Statement: (LeetCode 142) Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

This is the second phase of Floyd's Algorithm and requires a beautiful mathematical proof. The Insight: Let $L$ be the distance from the head to the start of the cycle. Let $C$ be the length of the cycle. When slow and fast intersect, they meet at a point inside the cycle. Due to the relative speeds (Fast is 2x Slow), the distance from the intersection point to the start of the cycle is EXACTLY EQUAL to the distance from the head to the start of the cycle ($L$)!

The Algorithm:

1. Run Fast & Slow until they meet.
2. Reset slow back to the head of the list. Leave fast at the intersection point.
3. Move BOTH pointers exactly 1 step at a time.
4. The exact node where they collide again is the start of the cycle!

public class CycleStartNode {
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        
        // Phase 1: Detect Cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) return null;
        
        // Phase 2: Find the Cycle Start Node
        slow = head; // Reset slow to start
        
        // Move both at the SAME speed
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // They meet exactly at the cycle entrance
        return slow;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Phase 1 takes at most $N$ steps. Phase 2 takes at most $N$ steps.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Incorrect while loop condition

   • The Mistake: while (fast != null) or while (fast.next != null) independently.
   • Why it's wrong: You must check BOTH. If fast is at the last node, fast.next is null. If you execute fast.next.next, it will throw a NullPointerException. If fast is null (because length is even), checking fast.next throws an NPE.
   • The Fix: ALWAYS use while (fast != null && fast.next != null).

2. Starting pointers at different locations

   • The Mistake: ListNode slow = head; ListNode fast = head.next;
   • Why it's wrong: While this still detects a cycle, it breaks the mathematical formulas used for finding the middle node or finding the cycle start node. Always start both at head (unless specifically required by a specialized edge case).

3. Comparing values instead of Nodes

   • The Mistake: if (slow.val == fast.val)
   • Why it's wrong: A cycle means the pointers are physically on the exact same object in memory. Comparing values will falsely trigger if the list is 1 -> 5 -> 3 -> 5 -> null. Compare the objects using ==.

7. Interview Q&A

Q1: How do you find the exact length of the cycle? Answer: First, run Floyd's to detect the cycle (find where slow == fast). Once they meet, pause slow. Move fast by 1 step at a time, incrementing a counter, until fast loops back around and hits slow again. The counter is the exact length of the cycle!

Q2: Can we move the fast pointer by 3 steps? Answer: Yes, a fast pointer moving 3 steps and a slow pointer moving 1 step will also mathematically guarantee finding a cycle. However, moving 2 steps is optimal because it guarantees they will meet in the fewest number of cycles (often on the very first lap). Moving by 3 can cause them to repeatedly "skip" over each other, delaying the collision.

Q3: How is this pattern used in "Happy Number" (LeetCode 202)? Answer: A Happy Number replaces a number with the sum of the squares of its digits. The problem asks if this process reaches 1 (Happy) or loops infinitely in a cycle (Unhappy). This is not a Linked List! But it IS a sequence of values that might loop. You can use Fast & Slow pointers! slow = getSum(n) and fast = getSum(getSum(n)). If slow == fast, a mathematical cycle exists and the number is Unhappy!

8. Practice Problems

1. Linked List Cycle (LeetCode 141)
   • Goal: Master the base algorithm.
2. Palindrome Linked List (LeetCode 234)
   • Hint: Use Fast/Slow to find the middle. Reverse the second half of the list. Compare the first half to the reversed second half!
3. Remove Nth Node From End of List (LeetCode 19)
   • Hint: A variation of this pattern! Move fast exactly $N$ steps ahead. Then move both slow and fast 1 step at a time. When fast hits the end, slow is perfectly positioned right before the node to remove!

9. Summary

• The Setup: ListNode slow = head; ListNode fast = head;
• The Core Loop: while (fast != null && fast.next != null)
• The Speed: Slow moves by 1, Fast moves by 2.
• The Cycle Start: A beautiful math trick. If they collide, reset slow to head, and move both by 1. Where they collide again is the start of the loop.