🚀 Fast & Slow Pointers (Floyd’s Cycle Detection Algorithm)

When working with linked lists or problems involving repetition of states (like circular arrays, number transformations, etc.), we often need to detect cycles.

A brilliant technique to handle this is the Fast & Slow Pointer Approach, also known as Floyd’s Tortoise and Hare Algorithm.

---

🔑 Intuition

• Use two pointers:

  • Slow pointer (slow) → moves 1 step at a time.
  • Fast pointer (fast) → moves 2 steps at a time.

• If there is a cycle, eventually fast will meet slow inside the cycle.

• If there is no cycle, fast will reach the end (null for linked lists or termination condition for arrays).

This works because in a cycle, the fast pointer laps the slow pointer after some iterations.

---

1️⃣ Detect Cycle in a Linked List

Problem

Given the head of a linked list, determine if it contains a cycle.

Code (Java)

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

public class CycleDetection {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;          // move by 1
            fast = fast.next.next;     // move by 2

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

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)

---

2️⃣ Find the Start Node of Cycle

Problem

If there is a cycle in a linked list, return the node where the cycle begins. If not, return null.

Idea

1. First detect if a cycle exists.
2. Once slow == fast inside the cycle, reset one pointer to head.
3. Move both one step at a time.
4. The node where they meet is the start of the cycle.

Proof Sketch

• Suppose the length before cycle start = L, cycle length = C.
• When slow and fast meet, slow has traveled L + k, fast L + k + m*C.
• Resetting one pointer to head makes them meet at cycle start after L steps.

Code (Java)

public class CycleStart {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head, fast = head;

        // Step 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Step 2: Find start of cycle
                ListNode ptr1 = head;
                ListNode ptr2 = slow;

                while (ptr1 != ptr2) {
                    ptr1 = ptr1.next;
                    ptr2 = ptr2.next;
                }
                return ptr1; // cycle start
            }
        }
        return null; // no cycle
    }
}

---

3️⃣ Happy Number Problem

Problem

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually leads to 1. Otherwise, it falls into a cycle (not happy).

Example:
19 → 82 → 68 → 100 → 1 (happy number)

Why Fast & Slow Pointers?

Because numbers that are not happy eventually form a cycle (never reaching 1).

Code (Java)

public class HappyNumber {
    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = sumOfSquares(n);

        while (fast != 1 && slow != fast) {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        }
        return fast == 1;
    }
}

✅ Time Complexity: O(log n) per step (since digit square sum has log n digits)
✅ Space Complexity: O(1)

---

📌 Additional Important Notes

• Why not use HashSet?

  • We could store visited nodes/numbers in a set to detect cycles.
  • But Floyd’s Algorithm is preferred for:
  • O(1) space (no extra memory).
  • Works well in memory-constrained or performance-sensitive environments.

• Where else is it used?

  • Detecting repetition in circular arrays.
  • Problems like Linked List Cycle II, Happy Number, Find Duplicate Number (without modifying array).

• Pitfall to Avoid:

  • Always check fast != null && fast.next != null before moving fast.
  • Otherwise, you risk NullPointerException.

---

🎯 Key Takeaways

• Fast & Slow pointers = elegant way to detect cycles.
• Works in O(n) time and O(1) space.
• Applicable beyond linked lists — works in number problems, arrays, and state transitions.

---