Delete the Middle Node of a Linked List
Medium · Linked Lists · Linked List · Two Pointers
Problem
You are given the head of a singly linked list with n nodes. Remove its middle node and return the head of the list that is left.
The middle node is node n // 2, counting from 0. With an even number of nodes that is the second of the two middle nodes: for 4 nodes it is node 2. A list with a single node becomes empty, so return None.
Examples
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6]
Seven nodes: the middle is node 3, with value 7.
Input: head = [1,2,3,4] Output: [1,2,4]
Four nodes: the middle is node 2, with value 3.
Input: head = [5] Output: []
The only node is the middle; nothing is left.
Constraints
- 1 <= number of nodes <= 10^5
- 1 <= Node.val <= 10^5
Approaches
- Count, then walk to the node before the middle — time O(n), space O(1)
Follow-up
The same walk answers related edits: deleting the middle k times removes one contiguous block, and inserting at the middle uses the same pointer that stops before it. Both are use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
