Find Middle of Linked List, in depth: slow and fast pointers, the two even-length middles and safe splits

Which middle

Number the nodes 0 to n − 1. For odd n there is one middle, index (n − 1) / 2. For even n there are two candidates, and you have to choose:

Neither is more correct; they answer different questions. The second middle is where the second half begins when the first half is the smaller one. The first middle is the last node of a first half that is never smaller than the second. Write down which one your caller needs before writing the loop, and name the function after it.

The two-pass baseline

The obvious approach counts the nodes and then walks to the chosen index. It is correct, easy to review, and needs no cleverness:

def middle_by_count(head):
    n, node = 0, head
    while node:
        n, node = n + 1, node.next
    node = head
    for _ in range(n // 2):        # (n - 1) // 2 for the first middle
        node = node.next
    return node

It reads n + n/2 links. Keep it in mind, because the two-pointer version is not cheaper in link reads; its advantages lie elsewhere, and it is worth being honest about that before an interviewer or a reviewer asks.

The slow and fast invariant

Run two pointers from the head. On each step, slow advances one node and fast advances two. After k steps, slow is at index k and fast is at index 2k. That is the whole invariant: slow is at half of fast's index.

The loop continues while fast can take two more steps safely, that is while fast and fast.next are both non-null. With fast at index 2k, both exist exactly when 2k + 1 < n, so the loop stops at the first k where 2k + 1 ≥ n, which is k = n // 2. Slow is then at index n // 2: the second middle.

Start fast one node ahead, at head.next, and the invariant shifts by one: fast sits at index 2k + 1. The same test now stops at the first k where 2k + 2 ≥ n, which is k = (n − 1) // 2: the first middle. Testing fast.next and fast.next.next with fast starting at the head is an equivalent way to write the same thing. The arithmetic is short enough to redo at a whiteboard, and doing it beats memorising which variant does what.

Implementation

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

def middle_second(head):
    """Index n // 2. Returns None for an empty list."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def middle_first(head):
    """Index (n - 1) // 2. Returns None for an empty list."""
    if head is None:
        return None
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

The same loop in Java, for the second middle:

static ListNode middleSecond(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Both functions handle the empty list and the single node without special cases beyond the guard in middle_first. Each uses O(1) extra space and runs in O(n) time, about n/2 iterations with three pointer reads each.

Worked example: six nodes

Here are the same traces as tables. With fast starting at the head, the loop runs 3 steps and returns node 3:

With fast starting at head.next, it runs 2 steps and returns node 2:

On a seven-node list there is one middle, and the second-middle loop runs 3 steps and returns node 3. Notice that in the even case the stopping condition fires on a different pointer: in the first table fast became null, in the second fast stopped on the last node. Both are covered by the single test fast and fast.next.

Splitting for merge sort

The commonest consumer is merge sort on a list, which cuts the list into two halves, sorts each recursively and merges. A cut after the middle sets mid.next = None and recurses on the head and on the old mid.next. This pairing needs the first middle. With the second middle, a two-node list returns node 1, the cut leaves halves of lengths 2 and 0, and the recursion on the left half is the same call again: infinite recursion, or a stack overflow, on any input with two or more nodes. With the first middle the halves are 1 and 1, and on six nodes they are 3 and 3; every split makes progress.

def split(head):
    """Cut a list of length >= 2 into two non-empty halves; return the second."""
    mid = middle_first(head)
    second = mid.next
    mid.next = None
    return second

def merge_sort(head):
    if head is None or head.next is None:
        return head
    second = split(head)
    return merge(merge_sort(head), merge_sort(second))

def merge(a, b):
    dummy = tail = Node(None)
    while a and b:
        if a.val <= b.val:            # <= keeps the sort stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

If you prefer the second middle, cut before it, which needs a prev pointer trailing slow. Either pairing works; mixing them is the bug. The palindrome check has the opposite preference: it reverses the list from the second middle onward and compares from both ends, and with an odd length the true middle is simply compared with itself or skipped.

Why use two pointers at all

If the two-pointer loop reads as many links as counting, why is it the standard answer? There are three real reasons and one false one.

• One pass, no length variable. The loop is a single traversal with no second phase, which matters when the code is embedded in a larger loop, and the result cannot be thrown off by a stale cached length.
• It generalises. Move fast three nodes per step and slow stops near the one-third point. Run fast k nodes ahead and move both at the same speed, and slow stops k from the end.
• It composes with cycle detection. The same two pointers are Floyd's cycle detector: if fast ever meets slow, the list has a cycle.
• False reason: it is faster. It is not, asymptotically or in link reads. On large lists the cost is dominated by cache misses on each node visit, which both methods incur, and two interleaved cursors may get slightly more out of the memory system than two sequential passes, but measure before you claim it.

Failure modes

These are the bugs that reach code review, and sometimes production.

• Wrong middle for the caller. The function returns the second middle and the caller cuts after it. Name functions by the middle they return, and test lengths 2 and 4.
• Cycles. On a cyclic list, while fast and fast.next never terminates. If inputs are untrusted, add the Floyd check: break with an error when fast is slow after a step.
• Null dereference. Testing only fast.next crashes on even lengths, where fast steps past the tail to null; test fast first, and in middle_first guard the empty list before reading head.next.
• Mutation during the walk. Another thread or an earlier step changes links while the loop runs; the invariant no longer holds. Linked lists are not safe to share without a lock.
• Recursion depth. Recursive merge sort on a list has depth about log2 n, which is fine; a recursive merge, often written for elegance, has depth n and overflows the stack on long lists. Merge iteratively, as above.

Testing the edges

Pin the behaviour with a property test against the counting definition, over every length from 0 up, rather than with two hand-picked examples:

def to_list(vals):
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head

def index_of(head, node):
    i = 0
    while head is not node:
        head, i = head.next, i + 1
    return i

def count(head):
    n = 0
    while head:
        head, n = head.next, n + 1
    return n

def test_middles():
    assert middle_second(None) is None and middle_first(None) is None
    for n in range(1, 200):
        head = to_list(list(range(n)))
        assert index_of(head, middle_second(head)) == n // 2
        assert index_of(head, middle_first(head)) == (n - 1) // 2

def test_split_progress():
    for n in range(2, 200):
        head = to_list(list(range(n)))
        second = split(head)
        a, b = count(head), count(second)
        assert a >= 1 and b >= 1 and a + b == n and a - b in (0, 1)

The split test encodes the property merge sort depends on: both halves are non-empty and the first is never smaller than the second. Add a test with a deliberately cyclic list if you added the cycle guard, and assert that it raises rather than hangs, with a timeout in the test runner.

Trade-offs and related reading

If you own the data structure and need the middle repeatedly, a size field plus a walk, or a different structure altogether such as an array-backed deque, beats any pointer trick. The pointer methods are for lists you are handed.

Related reading on this site: singly linked list operations for the basics, reversing a linked list for the second half of the palindrome check, Floyd cycle detection for the same two pointers used on cycles, and deep copying a list with random pointers for another pointer-discipline problem.

What to do next

1. Decide, for each caller, whether it needs the first or the second middle, and name the function accordingly.
2. Re-derive the stopping index from the invariant (slow at k, fast at 2k or 2k + 1) instead of trusting memory.
3. Pair a cut-after split with the first middle, or a cut-before split with the second and a prev pointer.
4. Add the property tests above for lengths 0 to a few hundred, plus the split-progress test.
5. Add a cycle guard if lists can come from untrusted or buggy producers.
6. Implement list merge sort and the palindrome check using your middle functions, and run them on lengths 1 to 4.
7. If you query the middle often on a list you own, keep a size field instead.