Fast & Slow Pointers Pattern

🐢🐇 Fast & Slow Pointers - Cycle Detection

1🐢🐇 Meet!

↰

(back to node 3)

Step 1: Start: Both pointers at head (node 1)

Progress: 1 / 5

Speed:

Legend:

Slow Pointer (🐢)

Fast Pointer (🐇)

Pointers Meet (Cycle!)

🎯 Explain Like I'm 5...

Imagine a turtle 🐢 and a rabbit 🐰 racing on a track. But wait! The track might be a circle that loops back!

🏃 The Race: Turtle takes 1 step at a time. Rabbit takes 2 steps at a time (he's faster!).

🔄 If the track is a circle:

• Rabbit runs faster and goes around the circle
• Eventually rabbit catches up to turtle from behind!
• When they meet → "Aha! This track is a circle!" 🎉

➡️ If the track is straight: Rabbit just runs to the end. They never meet!

🚀 Why use 2 speeds? If both moved at the same speed, they'd never meet even on a circle! The fast runner MUST catch up to the slow runner if there's a loop. It's like a faster runner lapping a slower runner on a race track!

When Should You Use This Pattern?

✓Detecting a cycle in a linked list
✓Finding the middle of a linked list
✓Finding where a cycle starts
✓Checking if a linked list is a palindrome

📝 Example 1: Detect Cycle in Linked List

Given a linked list, check if it has a cycle (where a node points back to a previous node).

CycleDetection.java

java

class ListNode {
    int value;
    ListNode next;
    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}
public class CycleDetection {
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;  // Empty or single node = no cycle
        }
        ListNode slow = head;      // 🐢 Turtle moves 1 step
        ListNode fast = head;      // 🐰 Rabbit moves 2 steps
        while (fast != null && fast.next != null) {
            slow = slow.next;           // Move slow by 1
            fast = fast.next.next;      // Move fast by 2
            // If they meet, there's a cycle!
            if (slow == fast) {
                return true;
            }
        }
        return false;  // Fast reached the end = no cycle
    }
    public static void main(String[] args) {
        // Creating a linked list with a cycle
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next;  // Creates cycle
        System.out.println("Has cycle: " + hasCycle(head));
        // Output: Has cycle: true
    }
}

📝 Example 2: Find Middle of Linked List

Find the middle node of a linked list in one pass.

FindMiddle.java

java

public class FindMiddle {
    public static ListNode findMiddle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head;  // 🐢 Moves 1 step
        ListNode fast = head;  // 🐰 Moves 2 steps
        // When fast reaches end, slow will be at middle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;  // This is the middle node!
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode middle = findMiddle(head);
        System.out.println("Middle value: " + middle.value);
        // Output: Middle value: 3
    }
}

📝 Example 3: Happy Number

A happy number eventually reaches 1 when you replace it with sum of squares of its digits. Example: 19 is happy (1² + 9² = 82, 8² + 2² = 68, ... eventually reaches 1).

HappyNumber.java

java

public class HappyNumber {
    // Calculate sum of squares of digits
    private static int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n = n / 10;
        }
        return sum;
    }
    public static boolean isHappy(int n) {
        int slow = n;           // 🐢 Turtle
        int fast = getNext(n);  // 🐰 Rabbit
        // If there's a cycle and it's not at 1, number is not happy
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);           // Move slow by 1
            fast = getNext(getNext(fast));  // Move fast by 2
        }
        return fast == 1;  // If fast reached 1, it's happy!
    }
    public static void main(String[] args) {
        System.out.println("Is 19 happy? " + isHappy(19));  // true
        System.out.println("Is 2 happy? " + isHappy(2));    // false
    }
}

🔑 Key Points to Remember

1️⃣Slow moves 1 step, Fast moves 2 steps
2️⃣If there's a cycle, they WILL meet eventually
3️⃣Time Complexity: O(n) - each node visited at most twice
4️⃣Space Complexity: O(1) - only two pointers needed!

💪 Practice Problems

• Find Cycle Start
• Palindrome Linked List
• Rearrange Linked List
• Cycle in Circular Array