#21EasyLinked lists

Merge Two Sorted Lists

The tell: Two sorted sequences to interleave into one sorted result.

How you get there

1A dummy head removes the special case of choosing the first node.
2Repeatedly attach the smaller head and advance that list.
3Attach whichever list remains — it is already sorted.

Solution

Python

def merge_two_lists(a, b):
    dummy = tail = ListNode()
    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        # attach the remaining tail
    return dummy.next

Time: O(n + m)
Space: O(1)

What goes wrong

Without a dummy node you need a separate branch to initialise the head, which is where bugs live.

Test yourself on DSA Next: Merge k Sorted Lists →