Middle of the Linked List
Return the middle node of a singly linked list. If there are two middles, return the second.
- The number of nodes in the list is in the range [1, 100].
- 1 <= Node.val <= 100
Intuition
Middle of the linked list returns the middle node, taking the second middle when the list has even length. The obvious method walks the list once to measure its length, then walks again to the halfway point — two passes, and correct.
The one-pass version uses two pointers moving at different speeds:
- Advance one pointer two nodes for every one the other moves; when the fast pointer reaches the end, the slow one is at the middle.
The arithmetic is simple — after k steps, fast has covered 2k nodes and slow has covered k, so slow is always at half the distance. When fast finishes at node n, slow stands at n/2.
The tie-break for even lengths falls out of the loop condition rather than needing a special case:
Looping while both fast and fast.next exist returns the second middle. Looping while fast.next and fast.next.next exist returns the first. That single difference is the whole control over which middle you get, so it is worth writing deliberately rather than discovering by trial.
Checking fast.next before taking the double step is also what prevents a null dereference — advancing two nodes blindly from the last node would fault.
This two-speed technique is the same one behind Linked List Cycle, Palindrome Linked List, and Reorder List. Recognising it makes those problems variations rather than separate puzzles.
Fast-and-slow pointers: move one pointer twice as fast, and when it reaches the end the slow one is halfway. The whole family — cycle detection, palindrome check, nth-from-end — runs on the idea that a relative speed or a fixed head start between two pointers encodes a position you'd otherwise need a second pass to find.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
See why one pass is possible
The two-pass version measures the length then walks halfway. Two pointers at different speeds compute the same position in one pass, since the slow pointer covers exactly half the distance the fast one does.
Advance at one and two steps
Move slow one node and fast two per iteration. After k iterations fast has covered 2k nodes and slow exactly k — the halving is built into the speed ratio.
Guard the double step
Loop while both fast and fast.next exist. Checking fast.next before advancing two nodes is what prevents a null dereference from the last node.
Control which middle you get
That loop condition returns the second middle on an even-length list. Looping on fast.next and fast.next.next returns the first. This single choice decides the tie-break — write it deliberately.
Return slow at the end
When the loop exits, slow is at the middle. No arithmetic or second traversal is needed — the position falls out of the speed ratio.
Recognise the shared technique
Linked List Cycle, Palindrome Linked List and Reorder List all use the same two-speed walk. Naming the pattern turns four problems into one technique with different endings.
Cost of the single pass
The fast pointer traverses the list once, giving O(n) time and O(1) space — the same time as the two-pass version with half the traversal and no length variable.
Solution & live demo
Common pitfalls
Checking fast.next before fast
while fast.next and fast:
while fast and fast.next:
On an even-length list fast becomes null, and evaluating fast.next first raises before the null check ever runs. Python's and short-circuits left to right, so the null test must come first.
Counting the length in a first pass
n = 0 while cur: n += 1; cur = cur.next for _ in range(n // 2): head = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.nextTwo passes, and it needs the list re-walked from the start. The speed difference computes the midpoint in a single traversal, which is the technique worth internalising.
Returning the first middle on even lengths
while fast.next and fast.next.next:
while fast and fast.next:
LeetCode asks for the second middle when the count is even — [1,2,3,4] should return node 3. The loop condition is what selects which of the two middles you land on.
Edge cases
fast stops at null after node 4; slow is at node 3 — the second of the two middles, as required.
The loop condition fails immediately; slow stays at the head and is returned.
One iteration moves slow to the second node, which is the correct middle.