Fast & Slow Pointers

The fast and slow pointers technique uses two pointers that move at different speeds (e.g. one step vs two steps per iteration). It is especially useful for linked lists and sequences where you need to detect cycles or find the middle.

When to Use

• Cycle detection in a linked list (or in a sequence that acts like a linked list via indices).
• Finding the middle of a linked list in one pass.
• Checking palindromes by moving from both ends toward the center.

Cycle Detection (Floyd’s Algorithm)

If a linked list has a cycle, a fast pointer (2 steps) and a slow pointer (1 step) will eventually meet inside the cycle. If there is no cycle, the fast pointer reaches the end.

JavaCopy
public 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;
    }
    return false;
}

To find the entry point of the cycle: after detecting the meeting point, reset one pointer to head and move both one step at a time until they meet again; that meeting point is the cycle start.

Finding the Middle

Move fast by 2 steps and slow by 1. When fast reaches the end, slow is at the middle (or the first of the two middle nodes for even length).

JavaCopy
public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Summary

Fast–slow pointers give O(n) time and O(1) extra space for cycle detection and middle finding. Use them whenever the problem involves cycles or “middle” in a linked list or index-based sequence.