Middle of the Linked List
Return the middle node of a singly linked list. If there are two middles, return the second.
Open on LeetCode ↗Intuition
Run two pointers, one twice as fast as the other. When the fast pointer reaches the end, the slow one — moving at half speed — sits exactly at the middle.
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
The two-pass version, and why one pass is possible
The straightforward way is to walk the list once to measure its length, then walk again to position length // 2. It's correct but takes two passes — and a singly linked list gives us no random access, so the second walk is unavoidable unless we find the middle without ever knowing the length.
Race two pointers at different speeds
Let a fast pointer move two nodes for every one node the slow pointer moves. When fast falls off the end, it has covered the whole list; slow, going half as fast, has covered exactly half — so it's sitting on the middle. We learned the midpoint relative to the end without ever computing the length.
Loop on fast and fast.next
Advance slow by 1 and fast by 2 while both fast and fast.next exist (so the double step is safe). Return slow. For an even-length list this naturally lands on the second of the two middles, which is what the problem asks. Single pass, O(n) time, O(1) space.
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.