Middle of the Linked List in One Pass

If you interview at Amazon, Google, Apple, expect some version of "Middle of the Linked List". It is rated Easy, and it falls squarely into the Fast and Slow Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 3 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a singly linked list, return the middle node; when there are two middles, return the second. Trivial with two passes (count, then walk) — the interview wants one pass, and the technique is a building block for three harder problems in this arc.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: node 3
For 1 -> 2 -> 3 -> 4 -> 5 -> 6 the answer is node 4 (second middle).

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

When fast finishes, slow — moving at half speed — sits at the midpoint. Any time a problem needs the middle, a split point, or the k-th node from a moving reference without knowing n, this invariant is the tool.

The Approach

Both start at head; slow steps once, fast twice, while fast and fast.next. On exit, slow is the middle — the second middle for even lengths, which conveniently matches the problem's convention.

If the first middle is wanted (as in Palindrome Linked List's split), change the condition to fast.next and fast.next.next. Knowing both variants cold prevents the fencepost fumble that eats five minutes live.

Python Solution

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def middle_node(head: ListNode) -> ListNode:
    """Second-middle node of the list (standard convention)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Complexity

• Time: O(n) — fast traverses the list once
• Space: O(1) — two pointers

Interview Tips and Follow-Ups

• Memorize the two loop conditions as a pair: fast and fast.next gives the second middle, fast.next and fast.next.next the first.
• This is a lemma, not a question: Palindrome Linked List, Reorder List, and sorted-list-to-BST all begin with exactly this code.
• If asked for the k-th from the end instead, the same idea becomes a fixed-gap two-pointer walk — Remove Nth Node, later in this arc.

More Fast and Slow Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.