Merge Two Sorted Lists

Problem

You are given the heads of two sorted linked lists l1 and l2. Merge them into a single sorted list by splicing the nodes (do not create new node values). Return the head of the merged list.

Example: 1→2→4, 1→3→4 → 1→1→2→3→4→4.

What the interviewer is testing

• Can you handle pointer manipulation without off-by-one errors?
• Do you use a dummy head node — the standard trick for the "first node has no predecessor" problem?
• Do you correctly attach the tail (the remaining list) without walking it?

Iterative solution — O(n + m) time, O(1) space

Use a dummy node so the first insert has a well-defined predecessor. Advance whichever pointer has the smaller value. When one list is exhausted, splice the other list wholesale onto the tail.

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

def merge_two_lists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2       # attach the remaining tail
    return dummy.next

Recursive solution — O(n + m) time, O(n + m) stack space

Elegant but uses stack proportional to the total length. In an interview the iterative version is usually the safer answer unless the interviewer explicitly asks for recursion.

def merge_two_lists(l1, l2):
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        l1.next = merge_two_lists(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists(l1, l2.next)
        return l2

Complexity — what to say out loud

"Time O(n + m) — every node is visited exactly once. Space O(1) for the iterative version because we're only rewiring existing nodes, not allocating."

Edge cases the interviewer will ask about

• One list is empty — early return, or the loop terminates immediately and we splice the non-empty one.
• Both lists are empty — dummy has no next; we return null.
• Equal values across lists — pick either; using <= keeps the merge stable relative to l1.
• Very long lists — O(1) space matters here; recursion would blow the stack.

Common follow-ups

• "Merge k sorted lists." — Use a min-heap of the current head of each list. O(N log k) where N is total nodes and k is number of lists.
• "Merge in place without a dummy node." — Doable but clumsy; explain that a dummy costs one node and avoids five special cases.
• "What if it's a doubly linked list?" — Same idea, just wire the prev pointer too when you set next.

How to verbalize your answer

"I'll use a dummy head node so I don't have to special-case the first insert. I walk both lists with two pointers, take whichever value is smaller, and advance that pointer. When one list is done, I splice the other onto the tail wholesale — no need to walk it. Time O(n + m), space O(1)."