Middle of the Linked List (LeetCode 876)

The problem

You get the head of a singly linked list. Return the middle node. If the list has an even number of nodes there are two middles; return the second one.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: node 3

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: node 4

With five nodes, node 3 has two nodes on each side. With six, the two middles are 3 and 4, and the problem asks for the second.

How to think about it

Start with brute force. Walk the list once to count its length n, then walk again n // 2 steps. That is O(n) time and O(1) space, so it is already fine. The only cost is two passes. A second brute force copies every node into an array and returns arr[n // 2], which is one pass but O(n) space.

The key insight: a pointer moving at double speed measures half the distance for you. If one pointer moves two nodes per step and another moves one, then when the fast one runs off the end, the slow one has covered exactly half the list. You never need to know n.

Why the loop condition gives the second middle. The loop runs while f and f.next. On an odd list, f lands on the last node and stops. On an even list, f jumps past the last node to None, which gives slow one extra step and leaves it on the second middle. If you wanted the first middle, you would stop one step earlier with while f.next and f.next.next.

Which pattern is this? Fast & slow pointers. The tell is “find a position defined by the length (middle, k-th from the end) in one pass without counting”.

Approach

1. Put both s (slow) and f (fast) on head.
2. While f and f.next both exist, move s one step and f two steps.
3. When the loop stops, f is on the last node (odd length) or None (even length).
4. Return s, which is the middle (the second middle for even lengths).

Solution

def middle_node(head):
    s = f = head
    while f and f.next:                # fast can still take two steps
        s = s.next; f = f.next.next    # slow 1 step, fast 2 steps
    return s
# middle_node([1,2,3,4,5]).val -> 3   (for even length, returns the second middle)

Dry run

On 1 -> 2 -> 3 -> 4 -> 5:

The function returns node 3. On the six-node list, a third step moves s to 4 and f to None, so it returns node 4.

Complexity

• Time: O(n). Fast covers the list in about n/2 iterations, each doing constant work.
• Space: O(1). Only two pointers, no matter how long the list is.

Edge cases and pitfalls

• Empty list (head is None): the loop never runs and the function returns None.
• One node: f.next is None, so it returns the head.
• First vs second middle. Read the problem: this one wants the second. Mixing up the loop condition is the most common bug.
• Guard order matters. Write f and f.next, not f.next and f, or you dereference None on even lists.

Related problems

• Palindrome Linked List (LeetCode 234): find the middle first, then reverse and compare.
• Reorder List (LeetCode 143): find the middle, reverse the back half, then weave.
• Linked List Cycle (LeetCode 141): the same two speeds, used to detect a loop.