65. Merge two Sorted Lists
Given the heads of two linked lists, list1 and list2, where each linked list has its elements sorted in non-decreasing order, merge them into a single sorted linked list and return the head of the merged linked list.
Example 1:
Input: list1 = head -> 2 -> 4 -> 7 -> 9, list2 = head -> 1 -> 2 -> 5 -> 6
Output: head -> 1 -> 2 -> 2 -> 4 -> 5 -> 6 ->7 -> 9
Explanation: head -> 1 -> 2 -> 2 -> 4 -> 5 -> 6 ->7 -> 9, the underlined nodes come from list2, the others come from list1.
Example 2:
Input: list1 = head -> 1 -> 2 -> 3 -> 4, list2 = head -> 5 -> 6 -> 10
Output: head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 10
Explanation: head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 10, the underlined nodes come from list2, the others come from list1.
Now Your Turn!
Pick the correct output for the given inputInput: list1 = head -> 0 -> 2, list2 = head -> 1 -> 3 -> 5 -> 6
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 0 <= number of nodes in list1, list2 <= 5 * 104
- -104 <= ListNode.val <= 104
- list1 and list2 are sorted in non-decreasing order.