Delete the Middle Node of a Linked List
Delete the Middle Node of a Linked List: remove the node at index ⌊n/2⌋ (0-indexed) and return the modified head.
- The number of nodes is in the range [1, 10⁵].
- 1 <= Node.val <= 10⁵
Intuition
You cannot index into a linked list, and counting first means two passes. Instead run a fast pointer at double speed: when it reaches the end, the slow pointer sits at the middle. Keep one node behind slow so the deletion is a single pointer rewrite.
Fast and slow pointers are the standard answer to any 'find a position defined by a fraction of the length' question on a linked list — middle, cycle start, n-th from the end. The tell is needing a positional target without a known length. The extra prev pointer is the deletion-specific addition.
Approach
Before reading on: if one pointer moves twice as fast as another, where is the slow one when the fast one finishes? Then work out what else you must hold on to in order to actually unlink a node. Aim for one pass, O(1) space.
Finding the middle without knowing the length
Advance slow one node and fast two nodes per iteration. Because fast covers twice the ground, when it runs off the end slow has covered exactly half — landing on index ⌊n/2⌋, which is precisely the node to delete. This is the tortoise-and-hare traversal, and it finds the middle in a single pass without ever computing the length.
Why you must track the previous node
Deleting from a singly linked list means making the predecessor skip over the target: prev.next = slow.next. Since you cannot walk backwards, prev has to be maintained as you go — one node behind slow at all times. Without it you would have the middle node in hand but no way to detach it, which is the most common stumbling block on this problem.
The loop condition and the single-node case
Use while fast and fast.next so fast.next.next is never dereferenced on a null. For a list of one node the middle is the head itself and the answer is an empty list, so return None immediately — the general loop cannot express that, because there is no predecessor to rewrite. Everything else is handled uniformly: O(n) time, O(1) space, one pass.
Solution & live demo
Common pitfalls
Not keeping the previous node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow is the middle, but now what?prev = slow slow = slow.next
A singly linked list cannot be walked backwards, so without prev there is no way to bypass the middle node. You end up holding the right node with no means to remove it.
Wrong loop guard
while fast.next and fast.next.next:
while fast and fast.next:
The two forms stop at different places, so slow lands one node early on even-length lists — deleting index n/2 − 1 instead of n/2. The guard must match the definition of the middle you want.
Forgetting the single-node case
slow, fast = head, head # straight into the loop
if not head.next:
return NoneWith one node the loop body never runs, so prev stays None and prev.next raises an AttributeError. Deleting the only node must return an empty list.
Edge cases
The middle is the head; return null since deleting it empties the list.
⌊2/2⌋ = 1, so the second node is removed, leaving [1].
Fast stops on the last node and slow sits at index 2, the true centre.
Fast runs off the end and slow lands on index 2, the later of the two middles — which is what ⌊n/2⌋ specifies.
Only possible for n ≤ 2; prev.next becomes null and the list ends cleanly.