DSA Merging Two Sorted Lists

The problem

A sorted linked list holds its values in increasing order. The problem gives two such lists. The answer is one sorted list holding every node from both.

The merge reuses the existing nodes. It rewires their links into one chain. No values are copied into new nodes.

An empty list is a valid input. The answer then is simply the other list.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


cases = [
    ([1, 2, 4], [1, 3, 4], [1, 1, 2, 3, 4, 4]),
    ([2, 5], [1, 3, 4], [1, 2, 3, 4, 5]),
    ([], [1, 2], [1, 2]),
    ([5, 6], [], [5, 6]),
    ([], [], []),
]
for first, second, expected in cases:
    print("first", first, "second", second, "merged:", expected)

Read the first row slowly. Both lists hold a 1 and a 4. The merged list holds each value twice, once from each list.

The last row merges nothing with nothing. Its answer is the empty list.

Intuition

Only two nodes can ever be next. Each list is already sorted. So the smallest unplaced value always sits at one of the two fronts.

The front of a list is its first unplaced node. Every node behind a front is at least as large. No later node can jump the queue.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


first = build([1, 2, 4])
second = build([1, 3, 4])
print("front of first:", first.value)
print("front of second:", second.value)
print("smaller front:", min(first.value, second.value))

The first idea many people try ignores that fact. It gathers every value, sorts the values, and builds a fresh list. That works, but it sorts values that were never out of order inside their own lists.

Sorting also copies. The values move into a plain list, and new nodes are built for the answer. The original nodes are thrown away.

Brute force

The brute force follows that first idea. Collect all values from both lists. Sort the collection. Build a new chain from the sorted values.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def merge_brute(first, second):
    values = values_of(first) + values_of(second)
    values.sort()
    return build(values)

cases = [
    ([1, 2, 4], [1, 3, 4]),
    ([2, 5], [1, 3, 4]),
    ([], [1, 2]),
    ([5, 6], []),
    ([], []),
]
for first, second in cases:
    merged = merge_brute(build(first), build(second))
    print(first, "+", second, "->", values_of(merged))

Every case from the start of the article passes. The answer is right. The method still wastes work.

The sort compares values many times over. Its cost grows as O((n + m) log (n + m)) for lists of length n and m. The value list and the new nodes each cost O(n + m) extra space.

The optimal solution: weave the two chains

Attach the smaller front node to the merged chain, one node at a time, until one list runs out. That one sentence is the whole method.

A dummy head starts the merged chain. A dummy head is a throwaway node placed before the real first node. It gives the chain a fixed starting point while its real head is still unknown.

A tail pointer marks the last placed node. Each round compares the two fronts. The smaller front links after the tail, and that list steps forward.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def merge(first, second):
    dummy = Node(0)
    tail = dummy
    while first is not None and second is not None:
        if first.value <= second.value:
            tail.next = first
            first = first.next
        else:
            tail.next = second
            second = second.next
        tail = tail.next
    tail.next = first if first is not None else second
    return dummy.next

cases = [
    ([1, 2, 4], [1, 3, 4]),
    ([2, 5], [1, 3, 4]),
    ([], [1, 2]),
    ([5, 6], []),
    ([], []),
]
for first, second in cases:
    merged = merge(build(first), build(second))
    print(first, "+", second, "->", values_of(merged))

All five cases pass. Equal fronts take from the first list, because the test uses <=. Equal values therefore keep their original list order.

The final link does heavy lifting. When one list empties, the rest of the other list attaches whole. No node is visited one by one after that point.

Walkthrough

Watch the merge of [1, 3, 5] and [2, 4]. The printout shows the merged chain and both fronts after each placement.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


first = build([1, 3, 5])
second = build([2, 4])
dummy = Node(0)
tail = dummy
placed = []

def front(node):
    return node.value if node is not None else None

print("start: merged", placed, "fronts", front(first), front(second))
while first is not None and second is not None:
    if first.value <= second.value:
        tail.next = first
        first = first.next
    else:
        tail.next = second
        second = second.next
    tail = tail.next
    placed.append(tail.value)
    print("placed: merged", placed, "fronts", front(first), front(second))
tail.next = first if first is not None else second
print("attach rest: merged", values_of(dummy.next))

The placements alternate at first. The 1 comes from the first list. The 2 then beats the waiting 3.

The second list empties when its 4 is placed. The 5 attaches whole in the last step. No comparison is spent on it.

Complexity

The time cost is O(n + m) for lists of length n and m. Each comparison places exactly one node, and the final attach costs one link.

The space cost is O(1) beyond the lists themselves. The merge stores two front pointers, one tail pointer, and one dummy node.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def merge_comparisons(first, second):
    dummy = Node(0)
    tail = dummy
    comparisons = 0
    while first is not None and second is not None:
        comparisons += 1
        if first.value <= second.value:
            tail.next = first
            first = first.next
        else:
            tail.next = second
            second = second.next
        tail = tail.next
    tail.next = first if first is not None else second
    return comparisons

for size in [2, 4, 8, 16]:
    odds = list(range(1, 2 * size, 2))
    evens = list(range(2, 2 * size + 1, 2))
    total = merge_comparisons(build(odds), build(evens))
    print("nodes per list", size, "total nodes", 2 * size, "comparisons:", total)

The counts stay below the node total. Sixteen nodes per side need thirty-one comparisons. The last node always attaches without one.

Doubling the input doubles the comparisons. The growth is a straight line. The brute-force sort grows faster than that line.

Edge cases and pitfalls

Two empty lists merge to an empty list. The loop never runs. The dummy head's next link stays None, and that None is the answer.

Forgetting the final attach is the classic bug. The loop alone drops every node of the list that did not empty. The walkthrough shows the attach placing the last node.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def merge(first, second):
    dummy = Node(0)
    tail = dummy
    while first is not None and second is not None:
        if first.value <= second.value:
            tail.next = first
            first = first.next
        else:
            tail.next = second
            second = second.next
        tail = tail.next
    tail.next = first if first is not None else second
    return dummy.next

print("both empty:", render(merge(build([]), build([]))))
print("first empty:", values_of(merge(build([]), build([1, 2]))))
print("second empty:", values_of(merge(build([5, 6]), build([]))))
print("equal fronts:", values_of(merge(build([1, 1]), build([1]))))
print("one node each:", values_of(merge(build([2]), build([1]))))

Equal fronts merge cleanly. Three nodes holding 1 become three nodes holding 1. No value is dropped or duplicated by the tie rule.

Moving the wrong pointer after a placement is the second pitfall. The tail must step onto the node just placed. Skipping that step overwrites the link and loses the node.