Merge Two Sorted Lists
You get the heads of two singly linked lists. Each list is sorted from smallest to largest.
Merge the two lists into one sorted list by relinking the existing nodes, and return the head of the merged list. Either input may be empty.
Examples
Input list1 = [1, 2, 4], list2 = [1, 3, 4]
Output [1, 1, 2, 3, 4, 4]
Input list1 = [], list2 = []
Output []
Input list1 = [], list2 = [0]
Output [0]
Constraints
- 0 <= length of each list <= 50
- -100 <= node value <= 100
- Both lists are sorted in non-decreasing order
Stuck? Take one hint at a time
Common mistakes
- Forgetting to attach the rest of the other list when one list runs out, which drops nodes.
- Using no dummy node and then special-casing the first node.
- Creating new nodes instead of relinking the existing ones, which uses O(n + m) extra memory.
- Comparing the nodes instead of their values.
Questions an interviewer may ask next
- Merge k sorted lists. (A min heap of the k current heads, or merge in pairs.)
- Merge two sorted arrays in place when the first has room at the end. (Merge from the back.)
- Remove duplicates while merging.
- Merge two sorted lists in descending order.
list1
[1,2,4]
list2
[1,3,4]
Expected output
[1,1,2,3,4,4]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.