Coding Interview Patterns

Fast & Slow Pointers

Floyd's tortoise-and-hare: two pointers advancing through a sequence at different speeds detect cycles and locate midpoints in O(n) time and O(1) space — no extra memory required.

Classic use: detecting a cycle in a linked list — if a cycle exists, the fast pointer (2 steps) always laps the slow one (1 step)
Finding the middle of a list in a single pass: when fast reaches the end, slow is at the midpoint
Finding the cycle start: after they meet, reset one pointer to the head and advance both one step at a time — they meet again exactly at the cycle's start (a consequence of the arithmetic, not a coincidence)
O(1) space beats the alternative of storing every visited node in a HashSet to detect a repeat
Generalizes to any "functional graph" (each node has exactly one outgoing edge) — e.g. detecting a cycle in repeatedly applying a function, like the "happy number" problem

Linked-list cycle detection

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

Fast/slow pointers vs a hash set
Approach	Time	Space
Fast/slow pointers	O(n)	O(1)
HashSet of visited nodes	O(n)	O(n)