Merge two sorted lists
You get list1 and list2, the first nodes of two linked lists. Each node is a ListNode with a value (node.val) and a link (node.next) to the node after it. Each list is sorted from smallest to largest (a value may repeat), and either one may be empty (None).
Combine them into one list sorted from smallest to largest and return its first node, or None if both lists are empty. The answer must be made of the nodes you were given, relinked by changing their next links, not of new nodes. When the two lists hold equal values, either node may come first.
Examples write a linked list as the list of its values: [1, 4, 6] means 1 → 4 → 6, and [] is an empty list.
list1 = [1, 4, 6], list2 = [2, 4, 5]Output[1, 2, 4, 4, 5, 6]Take the smaller front node each time. The two 4s end up next to each other.
list1 = [5], list2 = [1, 2, 3]Output[1, 2, 3, 5]Every node of list2 is smaller than 5, so list2 runs out first and the 5 goes on the end.
list1 = [], list2 = []Output[]Two empty lists merge into an empty list: return None.
0 ≤ number of nodes in each list ≤ 50
-100 ≤ node value ≤ 100
Each list is sorted from smallest to largest.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.