Delete the Middle Node of a Linked List
The key idea
Find the middle in one pass without counting the length: walk a fast pointer two steps for every one step of a slow pointer, so when fast reaches the end, slow sits on the middle. Track the node just before slow (prev) so you can splice the middle out with prev.next = slow.next.
Problem
You are given the head of a linked list. Delete the middle node and return the head of the modified list.
The middle node of a list of size n is the node at index floor(n / 2) using 0-based indexing, where floor(x) is the largest integer not greater than x.
For example, for n = 1, 2, 3, 4, 5 the middle indices are 0, 1, 1, 2, 2 respectively.
Constraints
- The number of nodes in the list is in the range [1, 10^5].
- 1 <= Node.val <= 10^5
Examples
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Input: head = [1,2,3,4]
Output: [1,2,4]
Input: head = [2,1]
Output: [2]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization