Problem · LC 21

Merge Two Sorted Lists

Easy
◧ Foundation · two pointers + dummy node

How to recognize it

Two sorted linked lists, merge them into one sorted list. The signal: "merge two sorted", "combine lists", or output should maintain sorted order. This is the core merge step in merge sort.

The core idea

Use a dummy node to simplify edge cases (no need to track the head separately). Maintain two pointers, one for each list. Compare values and attach the smaller to the result. Advance the pointer of the list we attached from. After one list is exhausted, attach the remaining of the other. Dummy node's next is the answer.

Why It's Tricky

Merging two lists feels like merging two arrays, but linked lists don't have random access. You must iterate and rearrange pointers, not shift elements. The dummy node trick eliminates the special case of finding the actual head.

The Key Insight

The dummy node is a game-changer: it lets you treat the head like any other node. You don't special-case "what if the smaller node is the head?" — it all goes through the same logic. Return dummy.next at the end.

Step-by-Step Walkthrough

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

dummy = ListNode(0)
curr = dummy

Compare 1 vs 1: attach 1 from list1, curr→1, curr=1
Compare 2 vs 1: attach 1 from list2, curr→1, curr=1
Compare 2 vs 3: attach 2 from list1, curr→2, curr=2
Compare 4 vs 3: attach 3 from list2, curr→3, curr=3
Compare 4 vs 4: attach 4 from list1, curr→4, curr=4
list1 exhausted, attach rest of list2 (4)

Return dummy.next: 1→1→2→3→4→4

time O(n + m)
space O(1)
merge_two_sorted_lists
def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 if l1 else l2
    return dummy.next

Interview gotchas

  • After one list is empty, don't forget to attach the rest of the other list with curr.next = l1 or l2.
  • Dummy node must be initialized with a value (often 0); it's just a placeholder.
  • Return dummy.next, not dummy.
  • Don't accidentally modify the input lists; the problem usually doesn't care, but be aware you're rearranging pointers, not copying nodes.

💡 What to Say in the Interview

  • Say: "I'll use a dummy node to simplify the merge logic and avoid special-casing the head."
  • Explain: "I compare the heads of both lists and attach the smaller. Then move that pointer forward."
  • Edge case: "When one list is exhausted, I attach the entire remaining of the other — no need to merge."
  • Complexity: "O(n+m) time to visit each node once, O(1) space (reusing existing nodes)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.