TL;DR
Fast/slow pointers with a head-start offset — one pass, O(n) time, O(1) space.
Approach 1 — Brute force: two passes (count, then walk)
The direct translation of the definition: pass 1 counts n; pass 2 walks to the node at index ⌊n/2⌋ - 1 and bypasses its successor.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
n = 0
node = head
while node:
n += 1
node = node.next
if n == 1:
return None
prev = head
for _ in range(n // 2 - 1):
prev = prev.next
prev.next = prev.next.next
return head
Complexity: O(n) time, O(1) space.
This is a valid answer within the constraints. The single-pass version below is the common follow-up: find the middle without first computing n.
Approach 2 — Fast & slow pointers, single pass
The insight: move two pointers at different speeds (the tortoise-and-hare idea). fast advances two nodes per step and slow one, so when fast reaches the end, slow is at the middle. Deletion needs the node before the middle, so give fast a two-node head start; that shifts slow’s stopping point one node back.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return None # 0 or 1 node: deleting the middle empties the list
slow = head
fast = head.next.next # head start: slow will stop BEFORE the middle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next # unlink the middle
return head
Walkthrough on 1 -> 3 -> 4 -> 7 -> 1 -> 2 -> 6 (n = 7, delete index 3, value 7; indices shown):
| step | slow (idx) | fast (idx) |
|---|
| start | 1 (0) | 4 (2) |
| 1 | 3 (1) | 1 (4) |
| 2 | 4 (2) | 6 (6) |
loop ends (fast.next is None) | 4 (2) | — |
slow is at index 2, one before the middle; slow.next = slow.next.next bypasses index 3 → 1 -> 3 -> 4 -> 1 -> 2 -> 6.
flowchart LR
A["1 (0)"] --> B["3 (1)"] --> C["4 (2)"] --> D["7 (3)"] --> E["1 (4)"] --> F["2 (5)"] --> G["6 (6)"]
S["slow stops here"] -.-> C
M["middle, delete"] -.-> D
On 2 -> 1 (n = 2): fast starts at None, the loop never runs, slow (the head) bypasses index 1 → 2.
Complexity: O(n) time — fast traverses the list once. O(1) space.
Approach 3 — Dummy-node variant (same idea, no special cases)
The insight: hanging a dummy node in front of the head lets slow naturally stop one node before the middle without a hand-tuned offset, and makes the single-node list fall out of the general code instead of an early return.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
slow, fast = dummy, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next
return dummy.next
Walkthrough on a single node 5: slow = dummy, fast = 5, fast.next is None so the loop never runs; slow.next = slow.next.next sets dummy.next = None, and dummy.next (None) is returned — the empty list, no special case needed.
Complexity: O(n) time, O(1) space — identical to Approach 2. Use whichever version you find clearer.
Common pitfalls
- Stopping
slow on the middle instead of before it — a singly linked list can’t delete the node you’re standing on (there’s no back-pointer), so aim for index ⌊n/2⌋ - 1.
- Off-by-one on even lengths: for n = 4 the middle is index 2 (the third node), not index 1 — check your loop against n = 2 and n = 4 by hand.
- Forgetting the 1-node list: the answer is
None, and code without the guard (or a dummy) dereferences slow.next.next off the end.
- Advancing
fast without checking fast.next — None.next on odd/even boundary cases.
Pattern takeaway
Two pointers at different speeds locate a fractional position in a single pass: fast at 2× finds the halfway point, and offsetting one pointer’s start shifts which node you land on (before-middle vs. middle). The same offset idea — start one pointer as far ahead as you want to stop short of the target — also powers Remove N-th Node From End and Middle of the Linked List.