AI Hints
Home›DSA in Python Tutorial›Trees, Lists and Grids
DSA in Python · Lesson 110 of 132

Practice: Merge Sorted Lists

One node at a time.

⏱ 2 min read▶ Video at 2:11:25🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Merge Sorted Lists
From the video: Practice: Merge Sorted Lists
  • 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.

merge_lists.pypython
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])))
Output
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.

keyvalue
Dummya fake first node
tailthe end so far
Attachthe smaller front node
Leftoverstail.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
Next up: Practice: Rotting Oranges — BFS from many starts