Practice: Merge Sorted Lists
One node at a time.
You have two sorted linked lists. Merge them into one sorted list, by re linking the nodes, without creating new ones. It's like merging in merge sort, but with pointers.

- Two sorted linked lists
- Merge into one
- Re-link, don't copy
A dummy head
A useful trick is a dummy node, a fake start, so we never have to treat the first node specially. Tail points at the end of the merged list. Each step, we attach the smaller of the two front nodes, and move along. When one list runs out, we attach the rest of the other. Run it.
from node import Node, build, show
def merge(a, b):
dummy = tail = Node(0)
while a and b:
if a.value <= b.value:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
show(merge(build([1, 4, 7]), build([2, 3, 8, 9])))1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9
Also uses node.py
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
vals = []
while head:
vals.append(str(head.value)); head = head.next
print(" -> ".join(vals))The dummy node trick
Dummy nodes remove special cases at the head of a list. You build everything after the dummy, and return dummy dot next at the end. It's useful for merging, deleting, and partitioning lists. This merge is O of N plus M, and uses O of one extra space.
| key | value |
|---|---|
| Dummy | a fake first node |
| tail | the end so far |
| Attach | the smaller front node |
| Leftovers | tail.next = a or b |
Summary
Use a dummy head, attach the smaller node each time, then add the leftovers. Next, a grid problem that spreads like a virus.
Key takeaways- Dummy node
- Attach the smaller
- Add the rest