How do you find the middle node of a linked list in one pass?

The 30 second answer

I use two pointers, slow and fast, both starting at the head. Slow moves one node per step and fast moves two, so when fast reaches the end, slow is in the middle. That's one pass, O(n) time and O(1) space, without counting the length first. For an even-length list this version returns the second of the two middle nodes, so I'd confirm which one the interviewer wants.

Why it works. After k steps, slow has moved k nodes and fast has moved 2k. When fast can no longer move two steps, slow has covered half the list.

// Slow moves 1, fast moves 2. Even length returns the second middle.
static Node middle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
// middle(of(1, 2, 3, 4, 5)).val    -> 3
// middle(of(1, 2, 3, 4, 5, 6)).val -> 4

First middle instead of second. Start fast at head.next, or loop while fast.next != null && fast.next.next != null. Say which variant you chose, because it decides the answer for even lengths.

Where the same pattern shows up. Splitting a list for merge sort, checking whether a list is a palindrome (find the middle, reverse the second half, compare), and Floyd's cycle detection, where a fast pointer that meets the slow one proves there is a cycle.

Sources (1)

LeetCode 876: Middle of the Linked Listleetcode.com