Merge Two Sorted Lists
EasyA dummy head removes every empty-list edge case. Then just attach whichever front node is smaller.
dummy headtwo pointers
TimeO(n + m)
SpaceO(1)
Inputfirst sorted list | second sorted list
list A→→→null
a
1
3
5
list B→→→null
b
2
4
6
merged
Two sorted lists. Compare the two front nodes and take the smaller.
1 / 8
dummy = new Node(); tail = dummy
while a and b:
if a.val <= b.val: tail.next = a; a = a.next
else: tail.next = b; b = b.next
tail = tail.next
tail.next = a or b // attach the remainder
Why it matters
This merge step is also the core of merge sort and of merging k lists.
Keyboard
space play← → stepr restartctrl K search
More in Linked List
Next visualiser
Tree Traversals (Pre / In / Post)