Merge Two Sorted Lists

Hints

1. Decide what a single step is. At any moment you are looking at the front node of each remaining list. Exactly one of them belongs next in the output: the smaller one. Every step is that same comparison, so the loop body is "compare two heads, detach the winner, append it".
2. Use a dummy head. Create a throwaway node, point curr at it, and append to curr.next every time. This removes the "is this the first node?" branch entirely. Return dummy.next at the end, never dummy.
3. Stop when either list empties, not when both do. The loop condition is while list1 and list2. The moment one side runs out there is nothing left to compare, and continuing would dereference a null pointer.
4. Splice the remainder in one assignment. After the loop exactly one list is non-empty and it is already sorted and already linked. curr.next = list1 if list1 else list2 attaches the whole tail in constant time. No loop, no copying.
5. Prefer <= over < in the comparison. On equal values either choice produces a sorted list, but taking from list1 on ties keeps the merge stable, which means equal elements retain their original relative order. Stability is free here and is load-bearing when the nodes carry payloads.
6. For the recursive version, state the induction. The smaller head is the answer's head, and its next is the merge of everything that remains. Trust the recursive call to be correct on the smaller input and the base cases write themselves: an empty list merges to the other list.

Solution: two approaches

Approach 1 - Iterative with a dummy head: O(m + n) time, O(1) space

The canonical answer. One pass, one sentinel node, no special cases.

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

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    curr = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next

    curr.next = list1 if list1 else list2
    return dummy.next

Why the dummy earns its allocation: without it, the head of the result is whichever input head is smaller, so you need a branch before the loop to pick it, a second variable to hold it, and a guard inside the loop for the first iteration. The sentinel collapses all of that. Every iteration performs the identical operation curr.next = winner, and the real head is recovered at the end as dummy.next. One node of garbage in exchange for one less branch and one less class of bug.

Why the loop is O(m + n): each iteration detaches exactly one node from one input and appends it to the output, so the total number of iterations is bounded by the number of nodes consumed, which is at most m + n. The work per iteration is one comparison and two pointer writes, all constant. There is no nested loop and no scanning, so the total is linear in the combined length. Note this is a lower bound as well as an upper one: any correct merge must at minimum look at every node to place it, so O(m + n) is optimal.

Why the tail splice is constant time: the surviving list is still sorted and its nodes are still linked to each other. Appending it means writing one pointer, not walking it. Candidates who loop here turn an O(1) step into O(m + n) extra work and, worse, signal that they think of lists as sequences of values rather than as chains of pointers.

Why space is O(1): the only allocation is the single dummy node, and nothing else grows with input size. The returned list is built entirely from nodes that already existed. If you instead allocate a new node per element you are at O(m + n) space and you have failed the "splice the nodes" requirement in the statement.

Approach 2 - Recursive: O(m + n) time, O(m + n) stack

The same algorithm expressed as induction on list length. Shorter to read, more expensive to run.

def merge_two_lists_rec(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists_rec(list1.next, list2)
        return list1
    list2.next = merge_two_lists_rec(list1, list2.next)
    return list2

Why it is correct: the base cases are exact, since merging anything with an empty list yields that thing unchanged. For the inductive step, assume the recursive call correctly merges the strictly smaller input. The smallest remaining value across both lists is the smaller of the two heads, so that node must be the head of the merged result, and everything after it is by definition the merge of what remains. Pointing the winner's next at the recursive result and returning the winner is exactly that statement in code. The same induction pattern is laid out in recursion as induction.

Why it costs more: the recursion consumes one stack frame per node, so depth reaches m + n. At the stated constraint of 50 nodes each this is harmless. At ten thousand nodes it overflows CPython's default recursion limit of 1000 and raises, and there is no tail-call optimisation in Python to save you, since the call is not in tail position anyway (the return value is assigned before returning). Write the recursive version to show you can, then say why you would ship the iterative one. Is recursion slower than iteration works through where the real cost sits.

Complexity comparison

Edge cases to verify

• Both lists empty: the loop never runs, curr.next is set to None, and dummy.next is None. Correct without a special case.
• One list empty: the loop never runs and the tail splice attaches the whole non-empty list in one write.
• Equal values across lists: [1] and [1] yields [1, 1]. Both nodes survive; neither is deduplicated.
• One list entirely smaller: [1, 2, 3] and [9] drains list1 completely, then splices the single node.
• Single-node lists: [2] and [1] yields [1, 2], exercising the else branch on the very first iteration, which is where an off-by-one in a hand-rolled head assignment would show up.

Where beginners go wrong

• Returning dummy instead of dummy.next. The sentinel is scaffolding, not part of the building. Returning it prepends a phantom 0 to every answer, which passes any test that only checks length and fails every test that checks contents.
• Skipping the dummy and hand-rolling the head. It can be done, and it costs you a pre-loop branch to pick the smaller head plus a first-iteration guard inside the loop. Every linked-list construction problem is easier with a sentinel; this is the problem that teaches you the habit.
• Forgetting the tail splice. The loop exits as soon as one list empties, and without curr.next = list1 if list1 else list2 the remainder of the other list is silently dropped. The output is sorted and short, so it looks plausible, which is what makes the bug expensive.
• Looping to copy the tail. Correct but wasteful. The remaining nodes are already sorted and already chained, so one pointer write attaches all of them. Writing a loop here means you are thinking in values rather than in pointers.
• Forgetting to advance curr. If curr = curr.next is missing, every iteration overwrites the same next field and the result holds exactly one node. The loop still terminates because the input pointers advance, which makes it look like a data bug rather than a control bug.
• Copying values between nodes instead of relinking. Assigning curr.val mutates the caller's nodes and violates the splice requirement. Linked-list problems are pointer problems; the payload should never move.

Interview follow-ups to expect

• "Merge k sorted lists." Two good answers. Pairwise merging in rounds, halving the list count each time, gives O(N log k) where N is the total node count. Or push the k heads into a min-heap and pop the global minimum repeatedly, also O(N log k). The heap version is explained in when to use a heap instead of sorting.
• "What if the lists are doubly linked?" Same algorithm, but every splice now writes two pointers, since the appended node's prev must point back at curr. The dummy still works and the complexity is unchanged.
• "Merge in descending order." Flip the comparison to >=. The structure does not change, which is a good way to show you understand that the comparator is a parameter and not part of the algorithm.
• "Do it without a dummy node." Pick the smaller head first, store it as head, advance that list, then run the same loop with curr = head. Write it once so you can explain precisely what the dummy was buying.
• "Now sort a single unsorted linked list." This function is the merge step of merge sort. Split the list in half using fast and slow pointers, sort each half recursively, and merge. That gives O(n log n) time with O(log n) stack, which is the standard answer for sorting a linked list in place.
• "Deduplicate while merging." Before appending, compare the candidate value against curr.val and skip it if equal. One extra branch, still one pass, and it only works because the inputs are sorted.

Related reading

• Linked Lists: the module this belongs to, including why sentinels show up in nearly every construction routine.
• Reverse Linked List: the other fundamental pointer-rewiring drill, and the one that teaches you to hold three pointers at once.
• Sorting: where this merge step reappears as half of merge sort.