Module 11 · Linked Lists and Pointer Mutation

104. Find the Middle Node

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the middle node of a finite acyclic singly linked list. For even length, return the second of the two middle nodes. Return None for an empty chain. Return a node reference, not a copied value or list.

Examples

Example 1

list_values(middle_node(build_list([1,2,3,4])))
=> [3, 4]

Serializing from the returned node reveals the second-middle suffix.

Example 2

list_values(middle_node(build_list([1,2,3])))
=> [2, 3]

The odd-length list has one middle.

Example 3

middle_node(None)
=> None

There is no middle node.

Reveal the worked solution and reasoning

Why this mechanism works

Advance a slow pointer once for every two fast-pointer steps. Starting both at the head naturally chooses the second middle for even lengths. The loop guard must establish that both fast and fast.next exist before advancing twice.

State and boundaries

After t iterations slow has moved t links and fast has moved 2t links unless it reached None.

Protocol

Start slow and fast at head.
While fast and its next exist, move slow once and fast twice.
Return slow when fast cannot advance twice.

Visualization

1 -> 2 -> 3 -> 4
slow: 1 -> 2 -> 3
fast: 1 ------> 3 ------> None
return node 3

Python implementation

from structures import build_list, list_values

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

list_values(middle_node(build_list([1,2,3,4])))

L4 middle_node: slow = fast = head
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N1(val=1,next=N2,random=None)

L6 middle_node: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N1(val=1,next=N2,random=None)

L7 middle_node: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N3(val=3,next=N4,random=None)

L6 middle_node: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N4,random=None); fast=N3(val=3,next=N4,random=None)

L7 middle_node: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N3(val=3,next=N4,random=None); fast=None

Result: [3, 4]. Serializing from the returned node reveals the second-middle suffix.

list_values(middle_node(build_list([1,2,3])))

L4 middle_node: slow = fast = head
head=N1(val=1,next=N2,random=None); slow=N1(val=1,next=N2,random=None); fast=N1(val=1,next=N2,random=None)

L6 middle_node: slow = slow.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N1(val=1,next=N2,random=None)

L7 middle_node: fast = fast.next.next
head=N1(val=1,next=N2,random=None); slow=N2(val=2,next=N3,random=None); fast=N3(val=3,next=None,random=None)

Result: [2, 3]. The odd-length list has one middle.

Why the solution is correct

The pointer-distance relation holds after every iteration. For length 2m, slow reaches index m; for length 2m+1, it reaches index m. These are exactly the required second middle and unique middle positions.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Starting fast one node ahead changes even-length tie behavior. Accessing fast.next.next without guarding fast.next can fail.

Reasoning card

State: After t iterations slow has moved t links and fast has moved 2t links unless it reached None.

Invariant: When fast finishes, slow has traversed half as many nodes.

Decision to rehearse: Slow moves one step, fast two.

Finish: Return slow when fast cannot advance twice

Transfer exercise

Return the first middle of an even-length list and explain the changed initialization or stopping condition.