Merge Two Sorted Lists
EasyLinked lists
You get the heads of two singly linked lists, list1 and list2, each sorted from smallest to largest. Join them into one sorted list made of their nodes, and return its head.
Each node has a val and a next pointer. On this page a list is written as an array of its values, from head to tail, and [] is an empty list.
Examples
Input: list1 = [2, 5, 9], list2 = [1, 5, 7] Output: [1, 2, 5, 5, 7, 9]
The fronts are compared one pair at a time, and both 5s are kept.
Input: list1 = [], list2 = [3, 4] Output: [3, 4]
One list is empty, so the answer is the other one.
Constraints
- Each list has 0 to 50 nodes.
-100 ≤ node.val ≤ 100- Both lists are sorted in non-decreasing order.
Stuck?
Hint 1
The smallest value left is always at the front of one of the two lists. Take it, and repeat.
Hint 2
Start from a dummy node so the first pick is not a special case. When one list runs out, link the rest of the other one on in one step.
The idea
Both lists are sorted, so the smallest value not yet placed is always at the front of one of them. Compare the two fronts, move the smaller node onto the end of the answer, and repeat. The nodes are relinked, not copied, so the merge needs no extra space.
Time O(n + m)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
dummy is a spare node that sits before the answer, so linking the first node is no different from linking any other. tail is the last node of the answer so far, where the next node gets linked.
function mergeTwoLists(list1, list2) { const dummy = new ListNode(); let tail = dummy; while (list1 && list2) { if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } tail.next = list1 || list2; return dummy.next;}The trap
The loop that takes the smaller front is right, so the start of the answer looks perfect. But the loop ends the moment either list runs out, and the other list always has at least one node left then. Those nodes, the largest values, are never linked on, and when one list starts empty the answer comes back empty.
function mergeTwoLists(list1, list2) { const dummy = new ListNode(); let tail = dummy; while (list1 && list2) { if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } // forgets to link on whatever is left of the longer list return dummy.next;}