Weave Two Sorted Chains
EasyLinked ListFree
Problem
Two sensors each log readings into a singly linked list, already sorted in non-decreasing order.
Given the heads a and b, splice the nodes of both lists into one list sorted in non-decreasing order and return its head. Reuse the existing nodes; do not allocate new ones.
Example 1
- Input:
- a = [1, 4, 6], b = [2, 4, 9]
- Output:
- [1, 2, 4, 4, 6, 9]
Repeatedly take the smaller front node of the two lists.
Example 2
- Input:
- a = [], b = [0, 3]
- Output:
- [0, 3]
Constraints
- 0 ≤ nodes in each list ≤ 5000
- -10^4 ≤ node.val ≤ 10^4
- Both lists are sorted in non-decreasing order.
Hint
Show the first hint
The smallest node of the merged list must be the front of one of the two lists.
Walkthrough
How to approach it
01Clarify before coding
- Can either list be empty? Yes, both can: return the other one (or null).
- Must I reuse nodes? Yes, splice them; O(1) extra space.
- What about equal values? Either order is fine for equal values, the output values are identical.
02Brute force
Copy all values into an array, sort it and build a new list.
Cost: O((n + m) log(n + m)) time and O(n + m) space, and it ignores the fact that both inputs are already sorted.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.