Delete the Middle Node of a Linked List
Remove the middle node of a linked list in one pass by starting the fast pointer two nodes ahead, so the slow pointer stops on the node before the middle.
Problem Understanding
Delete the Middle Node of a Linked List (LeetCode 2095): given the head of a linked list of n nodes, delete the middle node and return the head. The middle node is at index ⌊n / 2⌋, counting from 0: for n = 1, 2, 3, 4, 5 that is index 0, 1, 1, 2, 2.
Examples: [1, 3, 4, 7, 1, 2, 6] → [1, 3, 4, 1, 2, 6]; [1, 2, 3, 4] → [1, 2, 4]; [2, 1] → [2].
The Intuition: Stop One Node Early
Middle of the Linked List finds the middle with slow and fast pointers. Here that is one node too far: to unlink a node you need its predecessor.
- Give fast a head start. Begin fast at
head.next.next, as if one round of the walk had already happened without moving slow. - Walk as usual. slow moves one, fast moves two, until fast cannot move twice more.
- Unlink. slow is now just before the middle, so
slow.next = slow.next.next.
The same predecessor trick is how Remove Nth Node From End of List removes a node in one pass.
Interactive Walkthrough
7 NODES · MIDDLE = INDEX 3
ONE NODE?
0
→
1
→
2
→
3
→
4
→
5
→
6
→
NULL
slow
:
fast
:
Deleted
:
Does head have a next node? Yes
Next
slow starts at head; fast starts two nodes ahead, at 4
head
slow is filled and fast is outlined. Watch slow stop one node before the middle, then the middle turn red as the arrow out of slow skips it. Try Two nodes, where fast starts at NULL.
Dry Run Table
Input: [1, 3, 4, 7, 1, 2, 6], n = 7, so the middle is index 3.
| Round | slow (index) | fast (index) |
|---|---|---|
| start | 1 (0) | 4 (2) |
| 1 | 3 (1) | 1 (4) |
| 2 | 4 (2) | 6 (6) |
fast is on the last node, so the loop stops. slow.next is 7 at index 3; skip it. Answer: [1, 3, 4, 1, 2, 6].
The Solution Template
Slow and fast pointers with fast starting two nodes ahead, then one pointer change.
Delete the Middle Node of a Linked List Code
1var deleteMiddle = function(head) {2 if (!head.next) {3 return null;4 }5 let slow = head, fast = head.next.next;6 while (fast && fast.next) {7 slow = slow.next;8 fast = fast.next.next;9 }10 slow.next = slow.next.next;11 return head;12};
Edge Cases & Common Mistakes
- One node: return null; there is no predecessor to relink.
- Two nodes:
head.next.nextis null, the loop never runs, and the second node is removed. - Starting both pointers at head: slow lands on the middle itself and you cannot unlink it without its predecessor.
- Even length: the middle is the second of the two middles, index n / 2.
- Memory in C and C++: LeetCode does not require it, but in your own code free the unlinked node.
Summary
Return null for a single node. Otherwise start slow at head and fast at head.next.next, walk them at speeds one and two, and unlink slow.next. One pass, O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet