Merge Two Sorted Lists

Both lists are already sorted, so the smallest remaining value is always at the front of one of them. Repeatedly pick the smaller of the two front nodes and splice it onto the result — no new nodes need to be allocated.

Recursive

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

At each step, compare the two heads and let the smaller one absorb the recursively-merged rest of the lists. The recursion depth equals the total number of nodes, so the call stack itself costs O(n + m) space even though no extra list nodes are created.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Clean and easy to prove correct by induction, but the recursion stack grows with the combined length of both lists — an iterative version avoids that entirely.

Iterative With Dummy Head

OptimalTime O(n + m)Space O(1)

Walk both lists with a tail pointer that always points at the last node placed into the result. A dummy sentinel node avoids special-casing “is this the first node?” — we just return dummy.next at the end. Once one list runs out, the rest of the other list is already sorted, so it can be attached directly.

class Solution:
    def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 or list2   # attach whichever list still has nodes
        return dummy.next

Tracing list1 = [1,2,4], list2 = [1,3,4]:

▲tail

1 / 6

Compare heads: 1 (list1) vs 1 (list2). Tie goes to list1 — attach it, advance list1.

Why it’s correct: at every step the smaller of the two current heads is guaranteed to be the smallest value not yet placed in the result, since both source lists are sorted — so the output is built in non-decreasing order by construction. Complexity: each node from both lists is visited and attached exactly once → O(n + m) time, O(1) extra space (we reuse the existing nodes, only the dummy sentinel is new) — optimal, since every node must be examined at least once.