Merge two sorted lists

Weave two sorted lists into one sorted list by always taking the smaller head.

Time O(m + n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Compare the two front nodes, attach the smaller one to the result, and advance that list. When one list runs out, the rest of the other is already sorted, so attach it whole.

Code

C++PythonC#

ListNode* mergeLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

def merge(a: ListNode | None, b: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    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.next = a or b
    return dummy.next

public static ListNode Merge(ListNode a, ListNode b) {
    var dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a ?? b;
    return dummy.next;
}

Tips

The dummy head removes the special case of choosing the first node.
This is the merge step of merge sort, done on nodes instead of array slots.

In the .NET library

a ?? b is the null-coalescing operator: it returns a unless a is null, in which case it returns b.