Patterns / Linked Lists & Fast/Slow Pointers

Linked Lists & Fast/Slow Pointers

Two pointers at different speeds detect cycles and find the middle of a list in one pass, with no extra space.

What it is

Linked-list problems revolve around careful pointer manipulation. The fast/slow (tortoise and hare) technique runs one pointer twice as fast as the other: when the fast pointer reaches the end, the slow pointer is at the middle; if there is a cycle, the fast pointer eventually laps the slow one and they meet. It answers structural questions about the list without allocating an auxiliary set.

When to use it — the signals

• "Detect a cycle" or find where a cycle begins.
• "Find the middle node" or the k-th from the end.
• Reversing, reordering, or splitting a list in place.

How it works

A representative implementation in Java:

// Detect a cycle (Floyd's tortoise and hare).
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;   // they met -> cycle
}
return false;

Complexity

O(n) time, O(1) space — the whole point is to avoid a visited set.

Common pitfalls

• Dereferencing fast.next without null-checking fast first.
• Losing the list by reassigning next before saving the following node.
• Off-by-one when locating the middle of even-length lists.

Practice problems

Classic problems where this pattern is the intended approach: Linked List Cycle, Middle of the Linked List, Reverse Linked List, Reorder List. Work through them on the Leet Study home page.