Merge Two Sorted Lists
Linked Lists: lesson 8 of 10
Zip two ordered chains together without allocating a single node.
Lesson 8 of 10 · 5 min
Merge Two Sorted Lists
Step 1 of 13
compares0new nodes0
Two chains, both already sorted. A dummy head waits below so the first node is not a special case.
The Idea
Both chains are already ordered, so you never compare more than their two front nodes. Take the smaller, advance that side, repeat.
Nothing is allocated: you are re-pointing next fields on nodes that already exist. A dummy head means the very first node is not a special case.
Real-World Example
Two sorted stacks of exam papers being combined into one. You look only at the top sheet of each pile, drop the lower name onto the new pile, and never once re-read the sheets underneath.
The Code
class Node:
def __init__(self, v, nxt=None): self.val, self.next = v, nxt
def merge(a, b):
dummy = tail = Node(0) # fake head: no "first node" special case
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 is always the last node taken
tail.next = a or b # one side ran out: append the rest whole
return dummy.next
def build(vals): return Node(vals[0], build(vals[1:])) if vals else None
node = merge(build([1, 4, 7]), build([2, 3, 9]))
while node: print(node.val, end=" "); node = node.next # 1 2 3 4 7 9Your turn
Put the steps in the right order.
- One list empties, so attach the whole remaining chain to tail in one write
- Compare the two front values and splice the smaller node onto tail
- Create a dummy node and point tail at it
- Move tail onto the node just taken, and that list on to its next
Mini quiz
1 / 3