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
class Solution:
def deleteMiddle(self, 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.
Nothing about the constraints kills this — it’s a perfectly valid answer. The refinement below exists because “find the middle without knowing n” is the classic single-pass follow-up interviewers push for.
Approach 2 — Fast & slow pointers, single pass
The insight: this is the tortoise-and-hare middle-finding technique (the same two-speed pointer idea as Floyd’s cycle detection, used here for positioning): a pointer moving 2 steps covers the list in the time a 1-step pointer covers half of it, so when fast hits the end, slow stands at the middle. Since deletion needs the node before the middle, give fast a two-node head start — that shifts slow’s landing spot 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
class Solution:
def deleteMiddle(self, 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.
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
class Solution:
def deleteMiddle(self, 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; pick whichever reads cleaner to you.
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 half-way point, and offsetting one pointer’s start shifts which node you land on (before-middle vs. middle). The general recipe — “give the runner a head start equal to how far short of the target you want to stop” — also powers Remove N-th Node From End and Middle of the Linked List.