Interview Concept: Fast and Slow Pointer Technique Explained

What Is the Fast & Slow Pointer Technique?

Two pointers move through a sequence at different speeds — typically slow advances one step and fast advances two. The changing gap between them reveals structure such as cycles and midpoints, using only O(1) extra space.

Common Use Cases

• Cycle detection: if fast ever meets slow, there is a cycle (Floyd’s Tortoise and Hare).
• Find the middle: when fast reaches the end, slow is at the middle.
• Nth node from the end: move fast n steps first, then move both until fast hits the end.
• Happy Number: detect a cycle in the sequence of digit-square sums.

Cycle Detection Template

Python

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Java

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;
}

C++

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Finding a Cycle’s Start

After the pointers meet, reset one pointer to the head and advance both one step at a time. They meet again exactly at the start of the cycle — a consequence of the distances involved.

Complexity

• Time: O(n)
• Space: O(1)

Key Takeaways

• Different speeds expose cycles and midpoints without extra memory.
• The "move fast ahead by n first" trick solves nth-from-end in one pass.
• Works on linked lists and on any implicit "next value" sequence.