310. Zip Sorted Chains
Two conveyor belts each carry parcels labelled with a weight, and on each belt the weights never decrease from the front to the back. The two belts must be merged onto one outgoing belt so that the weights still never decrease from front to back.
Given the heads a and b of the two sorted chains, splice their existing nodes together into one sorted chain and return its head. When two front nodes have equal weights, take the one from a first. Either chain may be empty, in which case the answer is simply the other one. Each chain holds at most 50,000 nodes.
Example 1
- Input:
- a = [3,9,14,22], b = [4,9,30]
- Output:
- [3,4,9,9,14,22,30]
- Explanation:
Taking the smaller front each time gives 3, 4, 9, 9, 14, 22, 30.
Example 2
- Input:
- a = [], b = [-7,-2]
- Output:
- [-7,-2]
- Explanation:
The first belt is empty, so the second belt is returned as it is.
Constraints
0 ≤ length of each chain ≤ 5 * 104
-104 ≤ node value ≤ 104
Both chains are sorted in non-decreasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m)
- Space
- O(1)