Merge Two Sorted Lists

Easy#21dummy head

You get two linked lists, each sorted from small to large. Join them into one sorted list made of their own nodes and return its head. Our example: 3 → 6 → 11 and 1 → 6 → 8 — the answer is 1 → 3 → 6 → 6 → 8 → 11.

21 Merge Two Sorted ListsWalkthrough · 1×

Example: list1 = 3 → 6 → 11 on top, list2 = 1 → 6 → 8 below; each node stands in the column of its place in the answer.

nonenonedummy3611168list2list1
waiting in list1 or list2front of list1 or list2smaller, takentailin the answer

A dummy node: the answer will hang off it, whichever list its first node comes from

01/33
restart · back · play · step
Speed
1function mergeTwoLists(list1, list2):
2 dummy = new node
3 tail = dummy
4 while list1 and list2 are not none:
5 if list1.val <= list2.val:
6 tail.next = list1
7 list1 = list1.next
8 else:
9 tail.next = list2
10 list2 = list2.next
11 tail = tail.next
12 tail.next = list1 if list1 is not none else list2
13 return dummy.next
state
tail
–
list1
3
list2
1
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The smallest node not taken yet is always at the front of list1 or list2, so comparing the two fronts picks the next node of the answer.
  2. The dummy stands before the answer, so the first node is appended like all the others. Here it comes from list2, and no extra check was needed for that.
  3. When one list runs out, the other one is still sorted and larger than everything taken: it goes on whole, in one move.

Complexity

Time O(n + m): every node is taken once. Memory O(1): the answer reuses the nodes, only the dummy is new.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.