Delete the Middle Node of a Linked List
Understanding the Problem
We have a singly linked list and need to delete the node at position floor(n/2) (0-indexed). So for a list of 7 nodes, the middle is at index 3. For a list of 4 nodes, the middle is at index 2. For a single node, the middle is at index 0, which means we delete the only node and return null.
A singly linked list has no random access, so reaching any position means walking from the head. Deletion adds a second requirement: removing a node rewires the next pointer of the node before it, so the traversal has to stop one node short of the middle.
That reduces the problem to finding position floor(n/2) - 1 efficiently. One option is to count the nodes first and walk there in a second pass. The other is to find it in a single traversal with slow and fast pointers.
Key Constraints:
Number of nodes in range [1, 10^5]→ A full traversal is unavoidable since there is no random access, and O(n) time handles 100,000 nodes comfortably. The question is how many passes the traversal takes, not whether we can beat O(n).1 <= Node.val <= 10^5→ Values play no role here. The middle is defined purely by position.n >= 1→ The list is never empty, but a single-node list is possible: its middle is the head itself, and deleting it returns null.
Approach 1: Two-Pass (Count then Delete)
Intuition
If we knew the total number of nodes n, we could compute the middle index and walk to the node before it. Two passes provide both pieces: the first counts the nodes, the second stops at position floor(n/2) - 1 and rewires its next pointer to skip the middle node.
One edge case needs separate handling: a list with a single node has its middle at the head, so we delete it by returning null before either pass runs.
Algorithm
- Traverse the entire list to count the total number of nodes
n. - If
n == 1, returnnull(the only node is the middle). - Calculate the middle index:
mid = n / 2. - Traverse the list again, stopping at node
mid - 1. - Set
node.next = node.next.nextto skip the middle node. - Return
head.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Two traversals of the list: one to count (n steps) and one to reach the middle (n/2 steps). Total is O(n + n/2) = O(n).
- Space Complexity: O(1). Only a few pointer variables and an integer counter. No additional data structures.
The counting pass exists only to locate the middle. The next approach finds it during the traversal itself, cutting the work to a single pass.
Approach 2: Slow and Fast Pointers
Intuition
Move a fast pointer two steps for every one step of a slow pointer. When fast reaches the end of the list, slow is at the middle.
Stopping at the middle is not enough, though: deletion needs the node before it. Starting fast two nodes ahead, at head.next.next instead of head, makes the loop exit one slow-step earlier. When fast runs out of list, slow is on the node before the middle instead of on the middle itself.
After i loop iterations, slow is at index i and fast is at index 2i + 2. The loop exits at the first i where fast sits on the last node or has moved past the end, which works out to i = floor(n/2) - 1 for every n >= 2. For n = 7, the loop exits at i = 2 with fast on the last node; for n = 4, it exits at i = 1 with fast past the end. Either way, slow stops on the predecessor of the middle node, so slow.next is always the node to delete and is never null.
Algorithm
- If
head.nextis null (single node), returnnull. - Initialize
slow = headandfast = head.next.next. - While
fastis not null andfast.nextis not null, advanceslowby one step andfastby two steps. - When the loop ends,
slow.nextis the middle node. Setslow.next = slow.next.nextto delete it. - Return
head.
Visualization and Code
Loading animation...
- Time Complexity: O(n). A single traversal: fast advances two nodes per iteration until it reaches the end, and slow covers about half the list alongside it.
- Space Complexity: O(1). Two pointer variables, no additional data structures.