Linked Lists Reversing and rewiring
298. Merge Two Sorted Lists
You are given list1 and list2, the head nodes of two singly linked lists. Each list is sorted in
non-decreasing order. Combine the two into one list sorted in non-decreasing order, made of the nodes of both
lists, and return its head.
Non-decreasing order means each value is at least the one before it, so equal values can sit next to each other. The answer keeps every node of both lists, duplicates included. Either list can be empty, and an empty list is a null head. If both are empty, return null.
The examples write a list as its values from the head on, so list1 = [1,4,6] is the list 1 → 4 → 6. The
output shows the list you return the same way, and an empty list as [].
Example 1
Input: list1 = [1, 4, 4, 9], list2 = [2, 4, 7, 12, 15]
[1,2,4,4,4,7,9,12,15]Explanation: The answer holds all nine nodes in order. Two of the three 4s come from list1 and one from list2,
and all three are kept.
Example 2
Input: list1 = [], list2 = [-3, 0, 8]
[-3,0,8]Explanation: list1 is empty, so the answer is list2 as it is.
Example 3
Input: list1 = [10, 20], list2 = [3, 5, 6]
[3,5,6,10,20]Explanation: Every value in list2 is smaller than every value in list1, so the answer is all of list2 followed
by all of list1.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes in each list ≤ 105-109 ≤ Node.val ≤ 109- Both
list1andlist2are sorted in non-decreasing order.
Clarifying questions
What you would ask an interviewer before writing any code.