Merge Two Sorted Lists#

Problem#

Given the heads of two sorted singly linked lists, merge them into one sorted list by splicing together their nodes, and return the head of the merged list.

Example#

Lists 1 -> 2 -> 4 and 1 -> 3 -> 4 merge into 1 -> 1 -> 2 -> 3 -> 4 -> 4. If one list is empty, the other list is the answer.

Optimal approach#

Use a dummy head node to avoid special-casing the first element. Keep a tail pointer starting at the dummy. Walk both lists together: compare the current node of each, attach the smaller one to tail.next, and advance that list. When one list runs out, attach the entire remaining tail of the other list in a single step because it is already sorted. Return dummy.next, which skips the placeholder.

This reuses the existing nodes, so it needs no extra list allocation.

Solution#

 1class ListNode:
 2    def __init__(self, val=0, next=None):
 3        self.val = val
 4        self.next = next
 5
 6
 7def merge_two_lists(a: ListNode | None, b: ListNode | None) -> ListNode | None:
 8    dummy = ListNode()
 9    tail = dummy
10    while a and b:
11        if a.val <= b.val:
12            tail.next = a
13            a = a.next
14        else:
15            tail.next = b
16            b = b.next
17        tail = tail.next
18    tail.next = a if a else b
19    return dummy.next
20
21
22def build(values):
23    head = None
24    for value in reversed(values):
25        head = ListNode(value, head)
26    return head
27
28
29def to_list(node):
30    out = []
31    while node:
32        out.append(node.val)
33        node = node.next
34    return out
35
36
37print(to_list(merge_two_lists(build([1, 2, 4]), build([1, 3, 4]))))
38# [1, 1, 2, 3, 4, 4]

Complexity#

• Time: O(n + m), where n and m are the two list lengths.
• Space: O(1), only pointer rewiring.

More at the linked lists topic. Keep working through the 60-day challenge.