Fast & Slow Pointers (Floyd's Cycle Detection)¶

Overview¶

Use two pointers moving at different speeds to detect cycles, find middle elements, or solve linked list problems efficiently.

When to Use¶

Cycle detection in linked list or array
Finding middle of linked list
Finding cycle start position
Palindrome linked list
Happy number problem
Finding duplicate number

Fast & Slow Pointers Step-by-Step

Key Concepts: - Without Cycle: Fast reaches end (null) before meeting slow - With Cycle: Fast eventually catches slow inside the cycle - Finding Middle: When fast reaches end, slow is at middle

Template Code¶

Detect Cycle in Linked List¶

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 1 step
        fast = fast.next.next;   // Move 2 steps

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

Find Cycle Start (Entry Point)¶

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

    ListNode slow = head;
    ListNode fast = head;

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

        if (slow == fast) {
            // Phase 2: Find entry point
            ListNode entry = head;
            while (entry != slow) {
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null;
}

Find Middle of Linked List¶

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

    return slow;  // For even length, returns second middle
}

// For first middle in even length list:
public ListNode firstMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

    return slow;
}

Happy Number¶

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

    do {
        slow = sumOfSquares(slow);
        fast = sumOfSquares(sumOfSquares(fast));
    } while (slow != fast);

    return slow == 1;
}

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

Find Duplicate Number (Floyd's Algorithm)¶

// Array where nums[i] ∈ [1, n], find the duplicate
public int findDuplicate(int[] nums) {
    // Treat array as linked list: i → nums[i]
    int slow = nums[0];
    int fast = nums[0];

    // Phase 1: Find intersection point
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // Phase 2: Find cycle entrance (duplicate)
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

Palindrome Linked List¶

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;

    // Find middle
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    ListNode secondHalf = reverseList(slow.next);

    // Compare halves
    ListNode p1 = head;
    ListNode p2 = secondHalf;
    boolean isPalin = true;

    while (p2 != null) {
        if (p1.val != p2.val) {
            isPalin = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }

    // Restore list (optional)
    slow.next = reverseList(secondHalf);

    return isPalin;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Reorder List (L0→Ln→L1→Ln-1...)¶

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    // Find middle
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    ListNode second = reverseList(slow.next);
    slow.next = null;  // Cut first half

    // Merge alternating
    ListNode first = head;
    while (second != null) {
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}

Find Cycle Length¶

public int cycleLength(ListNode head) {
    ListNode slow = head, fast = head;

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

        if (slow == fast) {
            // Count cycle length
            int length = 1;
            ListNode current = slow.next;
            while (current != slow) {
                length++;
                current = current.next;
            }
            return length;
        }
    }
    return 0;  // No cycle
}

Mathematical Proof (Cycle Detection)¶

Let:
- m = distance from head to cycle start
- k = distance from cycle start to meeting point
- L = cycle length

When they meet:
- Slow traveled: m + k
- Fast traveled: m + k + nL (n complete cycles)

Since fast = 2 × slow:
  m + k + nL = 2(m + k)
  nL = m + k
  m = nL - k

This means: starting from head and meeting point,
            both will meet at cycle start after m steps!

Time & Space Complexity¶

Problem	Time	Space
Cycle detection	O(n)	O(1)
Find cycle start	O(n)	O(1)
Find middle	O(n)	O(1)
Happy number	O(log n)	O(1)
Find duplicate	O(n)	O(1)
Palindrome list	O(n)	O(1)

Common Interview Questions¶

Linked List Cycle - Detect if cycle exists
Linked List Cycle II - Find cycle start node
Middle of Linked List - Return middle node
Happy Number - Sum of squares cycle
Find the Duplicate Number - O(1) space solution
Palindrome Linked List - Check if palindrome
Reorder List - Interleave first and second half
Remove Nth Node From End - Fast pointer n steps ahead
Intersection of Two Linked Lists - Find merge point
Circular Array Loop - Detect cycle in array

Tips & Tricks¶

Fast moves 2x slow is most common, but ratio can vary
To find Nth from end: advance fast N steps, then move both
For middle: when fast reaches end, slow is at middle
Cycle start finding: both pointers move 1 step in phase 2
Works for arrays too when elements form implicit links
Always handle edge cases: null, single node, no cycle