Middle of the Linked List

A linked list cannot tell you its length, and you cannot jump to position n/2. The two-pointer answer finds the middle in one pass, and the choice of loop condition decides which middle you get. That second detail is where the bugs live, and it is used again inside Palindrome Linked List and Reorder List.

The problem

Given the head of a non-empty singly linked list, return its middle node. If the list has an even number of nodes, there are two middles; return the second one.

• 10 → 20 → 30 → 40 → 50 → the node holding 30. Two nodes sit on each side of it.
• 10 → 20 → 30 → 40 → 50 → 60 → the node holding 40. The middles are 30 and 40, and the second is asked for.

Constraints: 1 to 100 nodes. Values can repeat.

Clarifying questions

• Which middle for an even length? The second one, as stated. Some versions ask for the first; the fix is one line, so confirm before coding.
• Return the node or the value? The node, so the caller can use the rest of the list from there.
• Can the list be empty? Assume at least one node, but make the code return None for an empty list anyway.
• One pass required? Ask. If not, the two-pass answer below is perfectly acceptable.

Approach 1: count, then walk

Walk the whole list once to count its nodes, n. Then walk again from the head, taking n // 2 steps.

1def middle_node_two_pass(head: ListNode | None) -> ListNode | None:2    """Count the nodes, then walk n // 2 steps from the head."""3    length = 04    node = head5    while node is not None:6        length += 17        node = node.next8    node = head9    for _ in range(length // 2):10        node = node.next11    return node

For 5 nodes, 5 // 2 = 2 steps lands on the third node, 30. For 6 nodes, 6 // 2 = 3 steps lands on the fourth node, 40, which is the second middle.

Time: O(n), about 1.5n steps. Space: O(1).

Nothing is wrong with this. It is not too slow for any constraint. It falls short only when you may read the list once: the data is a stream, or the interviewer asks for one pass. It is also the natural step before the pattern, so say it first.

The key insight

If one pointer moves twice as fast as another, then when the fast one has walked the whole list, the slow one has walked half of it. You never need the length. The fast pointer measures the list while the slow pointer keeps pace at half speed.

The only hard part is the finish line. Fast moves two steps at a time, so it can end in one of two places: on the last node (odd length) or just past it on None (even length). The loop condition decides which of those stops the loop, and so which middle slow is on.

Approach 2: fast and slow pointers

1. Start slow and fast at the head.
2. While fast and fast.next both exist, move slow one step and fast two.
3. When the loop stops, return slow.

1def middle_node(head: ListNode | None) -> ListNode | None:2    """One pass: when fast reaches the end, slow is in the middle (second middle if even)."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next6        fast = fast.next.next7    return slow

Dry run on 10 → 20 → 30 → 40 → 50:

Returns 30.

On 10 → 20 → 30 → 40 → 50 → 60:

Returns 40, the second middle.

Time: O(n). The loop runs n // 2 times, and each tick does a constant amount of work. Space: O(1).

Getting the other middle

To stop on the first middle of an even-length list, stop the loop one tick earlier: continue only while fast has two more nodes ahead of it.

1def end_of_first_half(head: ListNode) -> ListNode:2    """First middle for even lengths; the end of the first half. Needs a non-empty list."""3    slow = fast = head4    while fast.next is not None and fast.next.next is not None:5        slow = slow.next6        fast = fast.next.next7    return slow

The second form is what you use to cut a list in half: slow ends on the last node of the first half, so slow.next is the head of the second half. It reads fast.next on the first check, so it needs a non-empty list.

Edge cases

• One node. fast.next is None, the loop never runs, and the head is returned. Correct.
• Two nodes. The first version returns the second node; the second version returns the first. Both are "the middle" under their own rule.
• Empty list. The first version returns None safely. The second crashes on fast.next, so guard it.

Follow-ups

• "Return the first middle instead." Change the guard to fast.next and fast.next.next, as above.
• "Delete the middle node." You need the node before the middle. Start fast two steps ahead (fast = head.next.next) so slow stops one node early, then set slow.next = slow.next.next. Handle a one-node list separately.
• "Split the list into two halves." Use the first-middle version, save second = slow.next, then set slow.next = None.