Fast and slow pointers

Two pointers, two speeds

The two-pointer techniques of the arrays module work on linked lists too, with one restriction: a pointer in a singly linked list can only move forward, one node at a time. That rules out walking in from both ends, but leaves a powerful variant: two pointers that start together and move at different speeds, or start at different places and move together. Each solves a problem that would otherwise need either two passes or extra memory.

Finding the middle

To find the middle of an array you compute n // 2. A linked list doesn't know its length, and counting it first costs a full pass. Instead, start two pointers at the head and move slow one node per round and fast two. When fast reaches the end, slow has gone exactly half as far: it is at the middle.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow          # for even lengths, the second of the two middle nodes

The loop condition checks fast.next as well as fast, because fast jumps two nodes and must not step off the end in the middle of a jump. Splitting a list at its middle is the first step of several algorithms, including sorting a linked list with merge sort and the practice problem Reorder list.

The node n from the end

The second variant keeps the pointers a fixed distance apart instead of moving them at different speeds. To find the node n positions from the end, move a lead pointer n nodes ahead, then move lead and trail together until lead reaches the end. The gap between them never changes, so trail ends n nodes before the end.

To delete that node rather than read it, trail must stop one node earlier, at its predecessor. Starting trail at a dummy head does exactly that, and it also handles the awkward case where the node to delete is the head itself. One pass, two pointers, no special cases.

Detecting a cycle

A list whose last node points back into the list never ends: walking it loops forever. Such cycles appear through bugs, such as a node accidentally linked to an earlier one, and on purpose in structures like circular buffers. The straightforward test keeps a set of visited nodes and stops at the first repeat. That works in O(n) time but needs O(n) memory.

Floyd's cycle detection, also called the tortoise and the hare, needs two pointers. Move slow one node per round and fast two. If the list ends, fast reaches the end first and there is no cycle. If there is a cycle, both pointers eventually enter it and go round and round. Once both are inside, fast gains exactly one node on slow every round. The gap between them starts somewhere below the cycle's length and shrinks by one each round, so it must reach zero: they land on the same node. fast can't jump over slow, because jumping over would need a gain of two in a single round.

The trace above runs it on a list where node 5 points back to node 3. After three rounds, both pointers stand on node 4.

Where does the cycle start?

Floyd's algorithm has a second phase that finds the node where the cycle begins. Put one pointer back at the head, leave the other at the meeting point, and move both one node at a time. They meet exactly at the start of the cycle. In the trace, they meet at node 3.

The reason is a short calculation. Say the cycle starts a nodes from the head, the meeting point is b nodes into the cycle, and the cycle has length L. When they met, slow had walked a + b nodes, and fast had walked twice as far, 2(a + b). The extra distance fast covered, a + b, must be a whole number of laps, kL. So a = kL − b: walking a steps from the meeting point is the same as walking back b steps and then some full laps, which lands exactly on the start of the cycle. Walking a steps from the head also lands there. So the two pointers arrive together.

Check it on the trace: a = 2, b = 1, L = 3, and indeed 2 = 3 − 1.

Beyond linked lists

Floyd's algorithm works on anything that repeatedly applies a function to get the next value, not only on next pointers. The practice problem Find the duplicate number gives an array of n + 1 numbers between 1 and n. Treat each value as a pointer to an index: from index i, go to nums[i]. Because some value repeats, two indexes lead to the same place, which creates a cycle, and the start of that cycle is the duplicate. The same idea detects cycles in pseudo-random number generators and underlies Pollard's rho method for factoring integers.

All of these share the property that made fast and slow pointers attractive in the first place: O(n) time with only a couple of variables of memory, on structures you can walk but not index.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Fast and slow pointers from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function reverse_and_find_mid(head):
    slow = head; fast = head
    while fast != null and fast.next != null:
        slow = slow.next
        fast = fast.next.next
    prev = null; curr = slow
    while curr != null:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
 
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr != nullptr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

public class LinkedListSolver {
    public static class ListNode {
        int val; ListNode next;
        ListNode(int v) { this.val = v; }
    }
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next
 
def reverse_list(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.