Delete the Middle Node of a Linked List — Solution

Problem

Given a singly linked list, remove the node at the exact middle position and return the modified list. The middle is the ⌊n/2⌋-th node using 0-based indexing — so for a 7-node list the middle is at index 3, and for a 4-node list it is at index 2.

[1,3,4,7,1,2,6]

• Input: head = [1, 3, 4, 7, 1, 2, 6]
• Output: [1, 3, 4, 1, 2, 6]
• Explanation: The list has 7 nodes; ⌊7/2⌋ = 3, so the node at index 3 (value 7) is deleted.

If the list has exactly one node, the result is an empty list.

Intuition

The challenge is locating the middle in a single pass without knowing the length upfront. A fast pointer that moves twice as quickly as a slow pointer positions the slow pointer exactly at the middle when the fast pointer exhausts the list — the classic "tortoise and hare" pattern. We also need the node just before the middle so we can unlink it, which a trailing prev pointer provides.

Solution — Fast and Slow Pointers

Use three pointers: fast advances two nodes per step, slow advances one, and prev always trails one step behind slow. When the loop exits, slow is at the middle and prev is the node just before it. A dummy head handles the case where the middle is the original head (n = 1).

1. Create a dummy node pointing to head so deletions near the front work uniformly.
2. Initialize prev = dummy, slow = head, fast = head.
3. While fast and fast.next are both non-null: set prev = slow, advance slow one step, advance fast two steps.
4. When the loop ends, slow is at the middle node.
5. Unlink it: prev.next = slow.next.
6. Return dummy.next as the updated head.

1def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    dummy = ListNode(0, head)
3    prev = dummy
4    slow = head
5    fast = head
6
7    while fast and fast.next:
8        prev = slow           # keep prev one step behind slow
9        slow = slow.next
10        fast = fast.next.next
11
12    prev.next = slow.next     # unlink the middle node
13    return dummy.next

Time: O(n) — one complete pass through the list.
Space: O(1) — only a fixed number of pointers regardless of list length.

Complexity Summary

Common Mistakes

• Omitting the dummy node: When n = 1, the middle is the head itself; without a dummy predecessor you cannot delete the head and return null cleanly. dummy.next absorbs this case without any special branch.
• Reversing the prev/slow update order: prev = slow must happen before slow = slow.next. Writing them in reverse order means prev always equals the new slow, making it trail by zero steps instead of one.
• Starting fast at head.next: This shifts the fast pointer's headstart and causes slow to land one node past the true middle on even-length lists.
• Returning head instead of dummy.next: When the original head is deleted (n = 1), the variable head still points to the removed node. Only dummy.next reflects the updated list.
• Off-by-one on even-length lists: For n = 4, ⌊4/2⌋ = 2, which is the third node (0-indexed). Tracing through [1,2,3,4] by hand before coding catches this before it becomes a wrong submission.

Related Problems

• middle-of-the-linked-list — identical fast/slow pointer setup, except you return the middle node instead of deleting it; a perfect warm-up
• remove-nth-node-from-end-of-list — fast/slow variant where fast starts N steps ahead to reach the Nth-from-last node
• palindrome-linked-list — also locates the middle with fast/slow before reversing the second half to check symmetry
• reorder-list — splits the list at the middle using fast/slow, reverses the back half, then interleaves the two halves
• odd-even-linked-list — pointer manipulation that regrouping nodes by index parity, reinforcing multi-pointer linked list technique