Merge two sorted lists
Zip two sorted chains into one sorted chain by always attaching the smaller front node to a growing tail. About 14 minutes.
Hang the smaller front node
Two sorted chains each have their smallest value at the front. So the smallest value overall is one of those two fronts. Take it, hang it on the end of the answer, and step that chain forward. Repeat.
A dummy node gives the answer a starting place so the first hang is no special case. Keep a tail pointer on the last node of the answer so far.
if a.val <= b.val:
pick, a = a, a.next
else:
pick, b = b, b.nextFronts are 1 and 1. Equal, so take the first list's 1. Answer so far: 1.
When one list runs out
The loop ends as soon as either chain is empty. The other chain still holds values that are all at least as big as everything already placed, and they are in order. So there is nothing left to compare.
Hang the whole remaining chain on the tail in one move. If both started empty, the answer is empty, and the dummy's next is nothing.
leftover = a or b # whichever is left
One list is [1, 5] and the other is empty. What does the merge return?
- AThe first list unchanged, 1 then 5
- BAn empty list
- CAn error, since there is nothing to compare
Show the answer
The first list unchanged, 1 then 5. The loop never runs, and the leftover chain is attached whole.
Merge two sorted lists
You are given the heads of two singly linked lists, each sorted in non-decreasing order. Merge them into one sorted list by relinking the existing nodes, and return the head of the merged list.
list1 = [1, 2, 4], list2 = [1, 3, 4] → [1, 1, 2, 3, 4, 4]
0 ≤ nodes in each list ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000 · both lists are sorted