318. Pop the Middle
A playlist is stored as a chain of songs, each node holding a song's id and a link to the next one. The host wants to drop exactly one song: the one sitting in the middle of the playlist. Positions are counted from 0, and the middle node is the one at position floor(n / 2), where n is the number of nodes.
Given the head of the chain, remove the middle node and return the head of the updated chain. For a chain of four songs the node at position 2 goes; for a chain of five, the node at position 2 goes as well; a chain with a single node becomes empty. You are not told n, and the chain can contain up to 100,000 nodes, so aim for one pass without counting the nodes first.
Example 1
- Input:
- head = [8,6,4,2,9]
- Output:
- [8,6,2,9]
- Explanation:
There are five nodes, so the middle is at position 2 (value 4). Result: [8, 6, 2, 9].
Example 2
- Input:
- head = [3,5,7,9]
- Output:
- [3,5,9]
- Explanation:
With four nodes the middle is position 2 (value 7). Result: [3, 5, 9].
Constraints
0 ≤ chain length ≤ 105
-105 ≤ node value ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)