Middle of the Linked List: Fast and Slow Pointers

An array knows its length, so its middle is one index away. A singly linked list knows only its head. The fast and slow pointer technique finds the middle anyway, in a single walk and constant memory: two pointers leave the head together, one moving one node per step and the other two. When the fast one runs out of list, the slow one is standing in the middle. The idea is small, but it is the first step of several classic problems, and its loop condition is where most bugs live.

The problem it solves

"Return the middle node" is the direct version. The same step hides inside bigger questions:

• Is this list a palindrome? Find the middle, reverse the second half, compare.
• Sort a linked list. Merge sort splits at the middle, then merges.
• Reorder or delete. Interleave the two halves, or remove the middle node.

The obvious alternative is two passes: count the nodes, then walk n // 2 steps. That is also O(n) and moves about as many pointers in total, 1.5n hops either way. The fast and slow version wins on something else: it touches the list in one traversal, so it works when you can only walk once, and it fits inside a loop that is already doing other work.

The intuition

After s steps, slow has moved s nodes and fast has moved 2s. Fast stops when it cannot take another double hop, which happens after about n / 2 steps, so slow sits at about n / 2. The details are in the guard:

• while fast and fast.next checks that the two nodes fast is about to jump over exist. On an odd length it stops with fast on the last node; on an even length it stops with fast past the end. Slow lands on the second middle of an even list.
• while fast and fast.next and fast.next.next stops one jump earlier, so slow lands on the first middle. Palindrome checks and merge sort want this one, because the first half should not be longer than the second.

To delete the middle, you need the node before it, so start fast one double hop ahead: slow then trails the middle by one.

Watch it run

The animation uses the lesson's list, 10 → 20 → 30 → 40 → 50. Both pointers start on the head; slow takes one hop per turn, fast takes two. Guard first: fast and fast.next both exist, so a two-node jump is safe. One hop and two hops put slow on 20 and fast on 30. The guard passes again, and the next step puts slow on 30 and fast on 50. Now fast.next is empty, so the loop stops: fast covered four links and slow exactly half of them. Slow is standing on 30, the middle, found in one pass with no length counter.

The code

Both middles, on the lesson's odd list and on an even one:

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def middle(head):
    """Second middle on even lengths: fast needs two nodes left to jump."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def first_middle(head):
    """First middle on even lengths: stop one jump earlier."""
    slow = fast = head
    while fast and fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    return slow

print(middle(build([10, 20, 30, 40, 50])).value)                 # 30
print(middle(build([10, 20, 30, 40, 50, 60])).value,
      first_middle(build([10, 20, 30, 40, 50, 60])).value)      # 40 30

A palindrome check in O(1) extra space: find the first middle, reverse the half after it, walk both halves together, then reverse it back so the caller's list is unchanged:

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def is_palindrome(head):
    """Find the first middle, reverse the half after it, compare, then put it back."""
    if head is None:
        return True
    mid = first_middle(head)
    second = reverse(mid.next)
    a, b, same = head, second, True
    while b:
        same = same and a.value == b.value
        a, b = a.next, b.next
    mid.next = reverse(second)                                   # restore the caller's list
    return same

lst = build([3, 1, 4, 1, 3])
print(is_palindrome(lst), is_palindrome(build([1, 2, 2, 3])), values(lst))
# True False [3, 1, 4, 1, 3]

Deleting the middle node, with fast starting one double hop ahead so slow stops just before it:

def delete_middle(head):
    """Remove the (second) middle node: walk slow one node behind it."""
    if head is None or head.next is None:
        return None
    slow, fast = head, head.next.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    slow.next = slow.next.next
    return head

print(values(delete_middle(build([5, 8, 2, 9, 4, 7]))))       # [5, 8, 2, 4, 7]

Checked on 2,000 seeded random lists of length 0 to 60, a third of them forced to be palindromes, against a brute force that copies the values into a Python list and indexes it. The palindrome check must also leave the list exactly as it found it:

import random

random.seed(29)
ok = True
for _ in range(2_000):
    vals = [random.randint(0, 3) for _ in range(random.randint(0, 30))]
    if random.random() < 0.3:                                    # force some palindromes
        vals = vals + vals[::-1][random.randint(0, 1):]
    n = len(vals)
    head = build(vals)
    if n:
        ok &= middle(head).value == vals[n // 2]                  # brute force: index into a list
        ok &= first_middle(head).value == vals[(n - 1) // 2]
    ok &= is_palindrome(head) == (vals == vals[::-1]) and values(head) == vals
    ok &= values(delete_middle(build(vals))) == vals[:n // 2] + vals[n // 2 + 1:]
print(ok)                                                        # True

The complexity

• Time: O(n). Fast visits every other node and slow half of them.
• Space: O(1): two pointers, no copy of the list, no length counter.
• Palindrome check: O(n) time and O(1) extra space, against O(n) space for copying the values into an array and comparing it with its reverse.

Where it goes wrong

• Testing only fast.next. On an empty list, or after fast steps past the end, fast.next raises. Check fast first.
• Picking the wrong middle. On even lengths, middle returns the second of the two; merge sort on a list wants the first, or a two-node list never splits.
• Leaving the list reversed. A palindrome function that does not restore the second half silently corrupts its input.
• Starting at the wrong node for deletion. To unlink the middle you need its predecessor, which is why fast starts two nodes ahead there.

When it shows up in interviews

As "middle of the linked list", "palindrome linked list", "delete the middle node", "reorder list" and "sort list", which all start with the same two pointers. The same pattern with a different stopping rule finds cycles in Floyd's algorithm, and a merge sort on lists ends in merging two sorted lists. The patterns cheat sheet lists fast and slow pointers with the problems it cracks.

How to say it in an interview

"I'll use two pointers from the head: slow moves one node per step, fast moves two. The loop runs while fast and fast.next exist, so the double hop is always safe; when it stops, slow is at the middle, the second one on an even length. If I need the first middle, for splitting in merge sort or a palindrome check, I also require fast.next.next. It's one traversal, O(n) time and O(1) space. For a palindrome I reverse the second half from the middle, compare, and reverse it back."