Delete the Middle Node of a Linked List
Problem
Given the head of a singly linked list, delete the middle node of the linked list and return the head of the modified list. If there are two middle nodes, delete the second middle node.
- The number of nodes in the list is in the range [1, 10⁵]
- 1 ≤ Node.val ≤ 10⁵
Example
head = [1,2,3,4,5][1,2,4,5]The list has 5 nodes, so the middle node is the 3rd node with value 3. The algorithm uses two pointers: 'slow' moves one step at a time, 'fast' moves two steps. When 'fast' reaches the end, 'slow' points to the node before the middle (node 2). The algorithm deletes the middle node by skipping it, resulting in [1,2,4,5].
Approach
Straightforward Solution
A naive approach would count the total number of nodes in one pass, then traverse again to the middle node and delete it. This requires two passes over the list, which is less efficient.
Core Observation
The middle node of a singly linked list can be found by advancing two pointers at different speeds: a 'fast' pointer moving two steps per iteration and a 'slow' pointer moving one step. When the fast pointer reaches the end, the slow pointer will be just before the middle node.
Path to Optimal
The key insight is to use the two-pointer technique to find the middle node in a single pass. By initializing a dummy node before the head, the slow pointer can stop at the node immediately before the middle, allowing deletion by pointer reassignment without extra traversal.
Optimal Approach
PreviewUse a dummy node pointing to head. Initialize slow at dummy and fast at head…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm traverses the list once with the fast pointer moving two steps and the slow pointer moving one step, resulting in a single pass over the list.
Space
O(1)
Only a fixed number of pointers are used regardless of input size, so the auxiliary space is constant.
Pattern Spotlight
Linked Lists (Two-Pointer Slow-Fast Technique)
Use two pointers moving at different speeds to find the middle or specific positions in a linked list in a single pass, enabling efficient in-place modifications without extra space.
Solution
| 1 | class Solution: |
| 2 | def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]: |
| 3 | dummy = ListNode(0, head) |
| 4 | |
| 5 | slow = dummy |
| 6 | fast = head |
| 7 | |
| 8 | while fast and fast.next: |
| 9 | slow = slow.next |
| 10 | fast = fast.next.next |
| 11 | |
| 12 | slow.next = slow.next.next |
| 13 | |
| 14 | return dummy.next |
Step-by-Step Solution
Set Up Dummy Node and Initialize Slow and Fast Pointers
| 3 | dummy = ListNode(0, head) |
| 5 | slow = dummy |
| 6 | fast = head |
Objective
To prepare the linked list for safe deletion by creating a dummy node and positioning pointers to find the middle node efficiently.
Key Insight
Introducing a dummy node before the head allows the slow pointer to stop at the node immediately before the middle node, which is essential for deleting the middle node by pointer reassignment. Initializing slow at dummy and fast at head sets up the classic two-pointer traversal pattern that finds the middle in one pass.
Interview Quick-Check
Core Logic
The dummy node acts as a sentinel to handle edge cases uniformly, and initializing slow and fast pointers at different positions enables the two-pointer technique.
Common Pitfalls & Bugs
Starting both pointers at head can complicate deletion logic, especially when the list has only one or two nodes.
Traverse the List with Slow and Fast Pointers to Locate Middle
To advance the slow and fast pointers through the list such that slow ends up just before the middle node.
Delete the Middle Node by Reassigning Pointers
To remove the middle node from the list by skipping it in the pointer chain.
Return the Modified List Head
To return the head of the updated linked list after deletion.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
slow.next = slow.next.nextDelete the middle node by skipping it in the list.
Reassigning slow.next to slow.next.next removes the middle node from the list in O(1) time without additional traversal or memory.
slow = dummyInitialize the slow pointer at the dummy node.
Starting slow at dummy ensures it will stop at the node before the middle, which is necessary for deleting the middle node by pointer reassignment.
slow = slow.nextMove slow pointer one step forward.
Advancing slow by one step per iteration ensures it moves at half the speed of fast, positioning it before the middle node when fast reaches the end.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why is a dummy node used before the head in this algorithm?
See the answer with Pro.
Related Problems
Linked Lists pattern
Don't just read it. Drill it.
Reconstruct Delete the Middle Node of a Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Delete the Middle Node of a Linked List drill