Delete the Middle Node of a Linked List
Solve this Problemhead of a singly linked list, delete the middle node and return the head of the resulting list. If the list has two middle nodes (an even count), delete the second one.
This is finding the middle node plus one wrinkle: deleting a node means rewiring the next pointer of whatever comes before it, and a singly linked list can't look backward on its own. The optimal solution keeps a third pointer, prev, trailing one step behind slow throughout the same fast and slow pointerFast & Slow PointersTwo pointers start together but move at different speeds — typically one step vs. two steps per iteration. Because the faster one covers exactly double the distance, its position relative to the end tells you something useful about the slower one's position — here, that it's sitting on the middle. walk — so by the time fast runs out of room, prev is already exactly where it needs to be to snip the middle out. The one edge case is a single-node list, which becomes empty once its only node is removed.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
If the list has two middle nodes (an even count), delete the second one - ◆
Deleting the only node in a 1-node list should leave an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node deleteMiddle(Node head) { |
| 3 | if (head.next == null) { |
| 4 | return null; |
| 5 | } |
| 6 | |
| 7 | Node prev = null; |
| 8 | Node slow = head, fast = head; |
| 9 | while (fast != null && fast.next != null) { |
| 10 | prev = slow; |
| 11 | slow = slow.next; |
| 12 | fast = fast.next.next; |
| 13 | } |
| 14 | prev.next = slow.next; |
| 15 | return head; |
| 16 | } |
| 17 | } |
| 18 |
2head.next is not null — there is more than one node, so continue.
Approach & Solutions
Brute Force — Count Length, Then Traverse to the Predecessor of the Middle
GoodWalk the list once to count its length. The node to delete sits at 0-indexed position (length / 2) using integer division — that formula naturally lands on the second middle when the length is even. Walk a second time to the node just before it, then bypass the target. Correct, but it needs the full length before it can even start looking for the middle.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteMiddle(Node head) {
9 if (head.next == null) {
10 return null;
11 }
12
13 int count = 0;
14 Node curr = head;
15 while (curr != null) {
16 count++;
17 curr = curr.next;
18 }
19
20 int mid = count / 2;
21 curr = head;
22 for (int i = 0; i < mid - 1; i++) {
23 curr = curr.next;
24 }
25 curr.next = curr.next.next;
26 return head;
27 }
28}Optimal — Slow & Fast Pointers with a Trailing Prev
OptimalReuse the fast/slow pointer trick for finding the middle, but keep a third pointer, prev, one step behind slow at all times. Move slow one step and fast two steps until fast runs out of room — slow lands on the middle exactly like before, except now prev is already sitting right where it's needed: at the predecessor of the node being deleted. One pass, no length precomputation.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteMiddle(Node head) {
9 if (head.next == null) {
10 return null;
11 }
12
13 Node prev = null;
14 Node slow = head, fast = head;
15 while (fast != null && fast.next != null) {
16 prev = slow;
17 slow = slow.next;
18 fast = fast.next.next;
19 }
20 prev.next = slow.next;
21 return head;
22 }
23}