Merge Two Sorted Lists
EasyLinked List
You are given list1 and list2, the heads of two singly linked lists. Each list is sorted in non-decreasing order.
Merge them into one list that is also sorted in non-decreasing order and return its head. Build the result by relinking the existing nodes rather than creating new ones. Keep every value, including duplicates. If both lists are empty, return None.
Example 1
- Input:
- list1 = [1,3,5], list2 = [2,4]
- Output:
- [1,2,3,4,5]
- Explanation
- Comparing the two fronts each step takes 1, 2, 3, 4 alternately from each list, and the leftover 5 is attached at the end.
Example 2
- Input:
- list1 = [2,2,8], list2 = [1,2,9,10]
- Output:
- [1,2,2,2,8,9,10]
- Explanation
- The three 2s (two from
list1, one fromlist2) all appear. Oncelist1runs out after 8, the rest oflist2(9, 10) is appended as is.
Example 3
- Input:
- list1 = [], list2 = [4,6]
- Output:
- [4,6]
- Explanation
- With
list1empty, the merged list is simplylist2.
Constraints
- The number of nodes in each list is in the range
[0, 50] -100 <= Node.val <= 100list1andlist2are each sorted in non-decreasing order