Delete the Middle Node of a Linked List
Real-world version: Drop the Middle PalletThe statement here is our own: the same inputs, outputs and technique.
Pallets on a tow line are coupled nose to tail, each one hitched to the next. The line is handed to you as chain, the list of pallet tags read from the front of the line to the back, so chain[0] is the leading pallet.
Uncouple the middle pallet and close the gap by hitching its predecessor straight to its successor. Numbering the pallets 0, 1, 2, ... from the front, the middle pallet is the one at position floor(n / 2), where n is how many pallets are on the line. A line of one pallet loses that pallet and ends up empty.
Return the tags of the pallets still on the line, front to back. Aim for O(n) time and O(1) extra space beyond the line you return.
Examples
Example 1
- Input
- chain = [8, 5, 9, 2, 7]
- Output
- [8, 5, 2, 7]
Five pallets, so the middle one sits at position floor(5 / 2) = 2, which is the pallet tagged 9. Pallet 5 is hitched to pallet 2 in its place.
Example 2
- Input
- chain = [4, 6, 1, 3, 9, 5]
- Output
- [4, 6, 1, 9, 5]
Six pallets, so position floor(6 / 2) = 3 goes, which is the pallet tagged 3.
Example 3
- Input
- chain = [12]
- Output
- []
One pallet sits at position floor(1 / 2) = 0, so the line ends up empty.
Example 4
- Input
- chain = [7, 7]
- Output
- [7]
Two pallets, so position floor(2 / 2) = 1 goes, which is the second of the two identical tags. The remaining pallet keeps its place at the front.
Example 5
- Input
- chain = [10, 20, 30]
- Output
- [10, 30]
Three pallets, so position floor(3 / 2) = 1 goes, which is the pallet tagged 20.
Constraints
- 1 <= chain.length <= 10^5
- 1 <= chain[i] <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def drop_middle(chain: list[int]) -> list[int]:public int[] dropMiddle(int[] chain)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's