Fast & Slow Pointers

July 2026 · 20 min read

A singly linked list will not tell you how long it is. You cannot ask for its size, you cannot index into it, and walking it once to count only to walk it again to act is two passes over memory you have already paid to fetch. The fast-and-slow-pointer family removes the count. You run two cursors over the list at the same time — either at different rates, or at the same rate with a fixed head start — and arrange things so that when the leading cursor falls off the end, the trailing one is sitting exactly where you need it. One pass, no length, no arithmetic on counts you had to compute first.

This post builds the whole family from that single idea and then hands you a lookup table from problem phrasing to pointer configuration. Everything here is a prerequisite for the next post on cycle detection, which is the same trick pushed until it proves a theorem.

Why Two Cursors Beat Count-Then-Walk

The naive way to find, say, the middle of a list is to walk it once to get the length L, then walk again L/2 steps. That is correct and it is O(n) time, but it touches every node twice, and on a cold, fragmented list every touch is a potential cache miss (see Nodes, Pointers & Memory). Worse, it does not generalise: the moment the list is a stream you can only read once, or is circular so there is no length, count-then-walk is dead.

Two cursors fix both problems. If fast moves twice as fast as slow, then when fast has travelled the full length L, slow has travelled L/2 — the middle — and it did so in the same single sweep. The relationship distance(fast) = 2 · distance(slow) is an invariant that holds after every iteration, and every problem in this post is just a different choice of speed ratio or gap that makes some invariant land the trailing pointer on the answer.

Finding the Middle: Which Middle?

The canonical loop is four tokens of surprising subtlety:

ListNode* middle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;              // for even n, this is the SECOND middle
}

Trace the loop guard. fast advances two nodes per step, so it needs two nodes ahead of it to be safe: fast itself must be non-null (checked by fast) and fast->next must be non-null (so fast->next->next does not dereference null). When the list has odd length, fast eventually lands exactly on the last node, fast->next is null, and the loop stops with slow on the unique middle. When the list has even length, fast overshoots to null and the loop stops with slow on the second of the two middles. That is the detail that decides whether "delete the middle" and "split in half" are correct.

To land on the first middle for even n, give fast a one-node head start, or equivalently tighten the guard so the loop stops one iteration earlier:

ListNode* firstMiddle(ListNode* head) {
    if (!head) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head;
    // stop before fast reaches the last node on even n
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;              // for even n, this is the FIRST middle
}

Here is where each convention leaves slow for every small length. Read it once and never guess again.

Odd lengths agree (there is only one middle); even lengths differ by exactly one node. The animation below lets you watch both. Toggle the convention and the length — on the 6-node list the two conventions land a node apart; on 7 nodes they coincide.

Split, Delete, and Fractional Positions

Split a list into two halves. Merge sort on a list (covered in Sorting a Linked List) needs the list cut into halves that differ in size by at most one, with the left half no longer than the right. That is exactly the first-middle convention, and the split must sever the link so the two halves are independent lists:

// Returns the head of the second half; first half ends at nullptr.
ListNode* splitInHalf(ListNode* head) {
    if (!head || !head->next) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head->next;          // head start => slow ends at first middle
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* second = slow->next;
    slow->next = nullptr;                 // cut the list in two
    return second;
}

Delete the middle node. To unlink a node you need the node before it, so carry a prev pointer one step behind slow. This uses the second-middle convention because that is what the problem asks for:

ListNode* deleteMiddle(ListNode* head) {
    if (!head || !head->next) return nullptr;   // 1 node => empty
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* prev = nullptr;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = slow->next;
    delete slow;
    return head;
}

Fractional positions. The speed ratio is a dial. A fast that moves three nodes for every one of slow leaves slow at the one-third mark when fast reaches the end; run slow at two-thirds speed for the two-thirds mark. The guard must protect all three dereferences:

// slow ends near the 1/3 point: distance(fast) = 3 * distance(slow).
ListNode* oneThird(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next->next;
    }
    return slow;
}

All four routines are O(n) time and O(1) extra space. None of them ever learns the length.

The n-th Node From the End: Fixed Gap

The second family keeps both cursors at the same speed but opens a fixed gap between them. To find the n-th node from the end, advance fast by n nodes first, then move fast and slow together. When fast hits null, slow is n nodes from the end — because the gap never changed and fast is one-past-the-last.

ListNode* nthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    for (int i = 0; i < n; ++i) {
        if (!fast) return nullptr;        // list shorter than n: n is invalid
        fast = fast->next;
    }
    ListNode* slow = head;
    while (fast) {                        // stop when fast is null
        slow = slow->next;
        fast = fast->next;
    }
    return slow;                          // the n-th node from the end
}

The off-by-one lives entirely in where you stop. Advancing fast by n and then walking until fast == nullptr lands slow on the target. If instead you walk until fast->next == nullptr, slow stops one node earlier — on the target's predecessor. That is not a bug; it is precisely what you want when you intend to remove the n-th node, because deletion needs the node before it.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
    for (int i = 0; i < n; ++i) fast = fast->next;   // n assumed valid (1 <= n <= length)
    while (fast->next) {                              // stop on the node BEFORE the target
        slow = slow->next;
        fast = fast->next;
    }
    ListNode* victim = slow->next;
    slow->next = victim->next;
    delete victim;
    return dummy.next;
}

Notice the two loops stop at different places on purpose: nthFromEnd runs fast to null to return the target; removeNthFromEnd runs fast to the last node so slow lands on the predecessor to splice it out. If you need to validate n, the head-start loop is where you check it — if fast becomes null before you have advanced n times, the list is shorter than n and the request is invalid.

Palindrome Check: Middle, Reverse, Compare, Restore

Testing whether a list reads the same forwards and backwards in O(1) extra space is a three-act combination of everything so far: find the first middle, reverse the second half, walk the two halves in lockstep comparing values, and — if you are polite — reverse the second half again to leave the list as you found it.

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    // 1. first middle
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // 2. reverse the second half (see the reversal post)
    ListNode* second = reverse(slow->next);
    // 3. compare the two halves
    ListNode* p = head;
    ListNode* q = second;
    bool ok = true;
    while (q) {
        if (p->val != q->val) { ok = false; break; }
        p = p->next;
        q = q->next;
    }
    // 4. restore the list
    slow->next = reverse(second);
    return ok;
}

The comparison loop is driven by q (the reversed second half), which is the shorter or equal side, so it stops cleanly at the centre regardless of parity. The reverse helper is developed in Reversing a Linked List, and the elegant — if stack-hungry — recursive framing of this exact problem appears in Recursion on Linked Lists. The whole thing is O(n) time and O(1) space, versus the O(n)-space shortcut of copying values into an array.

Intersection of Two Lists: Equalising the Runways

Two singly linked lists that merge share a common tail from the intersection node onward — they form a Y, never an X, because a node has exactly one next. The elegant solution walks a pointer down each list and, on reaching the end, restarts it at the other list's head:

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* a = headA;
    ListNode* b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;                 // the intersection node, or nullptr
}

Why it works is a one-line proof. Let the pre-intersection lengths be p and q, and the shared tail length be c. Pointer a traverses p + c then switches and traverses q, reaching the intersection after p + c + q steps. Pointer b traverses q + c then p, reaching it after q + c + p steps. Those are equal, so both pointers arrive at the intersection node on the same step. If the lists never intersect, c = 0 and both become null after p + q steps — a == b == nullptr ends the loop. The check a ? a->next : headB is doing the work: crucially it steps to null before switching heads, which is what makes the disjoint case terminate instead of looping forever.

The Template: Phrasing to Configuration

Almost every "do it in one pass with O(1) space" list problem is one of a handful of pointer configurations. Match the phrasing to the row:

The last row is the bridge: the very same different-speed configuration that finds the middle also detects a cycle, because in a cycle a doubly-fast pointer must eventually lap a single-speed one. That collision, and the surprisingly deep proof that resetting one pointer to the head finds the loop's entrance, is the whole of the next post.

Check Yourself

You are given the situation; pick the configuration or conclusion that is actually correct.

Practice

• LeetCode 876 — Middle of the Linked List middle returns the second middle for even length — use while (fast && fast->next) as written.
• LeetCode 19 — Remove Nth Node From End of List gap anchor both pointers at a dummy head so removing the head is not special.
• LeetCode 2095 — Delete the Middle Node prev carry a trailing pointer and use the second-middle convention.
• LeetCode 234 — Palindrome Linked List reverse first middle, reverse the second half, compare, then restore.
• LeetCode 160 — Intersection of Two Linked Lists swap heads step to null before switching so disjoint lists terminate.
• LeetCode 141 — Linked List Cycle bridge the same slow/fast pair, but stop on collision instead of on null.