21. Merge Two Sorted Lists
You have two linked lists, list1 and list2, and each one is already sorted in non-decreasing order. Your job is to weave them into one sorted list by repeatedly taking whichever front node is smaller, and return the values of the combined list.
Either list (or both) may be empty. Your function receives the two lists as integer arrays of node values, in order, and returns the merged values as a single array — every element from both inputs, still sorted.
The merge step here is the heart of merge sort; do it without sorting from scratch.
Example 1:
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: Taking the smaller front value each time interleaves the two lists into 1, 1, 2, 3, 4, 4.
Example 2:
Input: list1 = [], list2 = [0]
Output: [0]
Explanation: list1 is empty, so the merged list is just list2.
Constraints:
- 0 ≤ list1.length, list2.length ≤ 100
- -100 ≤ node value ≤ 100
- Both list1 and list2 are sorted in non-decreasing order.
Hints:
Both lists are already sorted, so the smallest remaining value overall is always at the front of one of them.
Compare the two front values, take the smaller one, and repeat on what's left — that recurrence is a natural fit for recursion, or a simple two-pointer loop.
When one list runs out, everything left in the other list is already sorted — append it all at once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Expected output: [1, 1, 2, 3, 4, 4]