Merge Two Sorted Lists
Easy · linked list
You are given the heads of two singly linked lists, list1 and list2. Both lists are already sorted in non-decreasing order. Merge them into one sorted list and return its head.
Build the result by splicing together the existing nodes, not by creating new ones. If one list is empty, the answer is the other list. If both are empty, return None. The nodes you receive are ListNode objects with a val and a next.
Examples
Example 1
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
At every step you take the smaller front value, so the two lists weave together in order.
Example 2
Input: list1 = [], list2 = []
Output: []
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
One list is empty, so the other one is already the answer.
Constraints
- 0 <= number of nodes in each list <= 5000
- -5000 <= Node.val <= 5000
- Both lists are sorted in non-decreasing order.