4.9.2 — Merge Two Sorted Lists

LeetCode 21 · Easy · ★ Blind 75

The problem

Merge two sorted linked lists into one sorted list, by splicing the existing nodes rather than creating new ones.

1 → 2 → 4
1 → 3 → 4
becomes
1 → 1 → 2 → 3 → 4 → 4

The pattern

Walk both lists at once. Whichever head is smaller gets attached to the result, and that list advances. Repeat until one list runs out, then attach whatever remains of the other.

This is the merge step of merge sort (4.10), and it is why merge sort works well on linked lists — the merge needs no extra array, just pointer rewiring.

The dummy head

The first node is awkward. Every later node is attached with tail.next = node, but the first one has no tail to attach to, so you would need an if on the very first iteration.

The fix is a fake node in front of the list. Attach everything to it, including the first real node, and return dummy.next at the end.

dummy → 1 → 1 → 2 → 3 → 4 → 4
  ↑
  never part of the answer, just something to attach to

The dummy head removes special-casing the head from every linked-list problem where nodes are added or removed. It is the single most useful habit in this chapter, and it appears again in 4.9.4, 4.9.6 and 4.9.11.

The solution

Python

class Solution:
    def mergeTwoLists(self, list1, list2):
        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 whatever is left

        return dummy.next

TypeScript

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;

  while (list1 && 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 ?? list2;

  return dummy.next;
}

tail.next = list1 or list2 handles the leftovers in one line. When the loop ends, at least one list is null. Whichever is not null is already sorted and already longer than everything placed so far, so it can be attached whole. No loop needed. In Python or returns the first truthy value; in TypeScript ?? returns the first non-null.

<= rather than < keeps the merge stable — when values are equal, the node from the first list goes first. It makes no difference to correctness here, but stability is the property that makes merge sort useful on records with keys, so it is worth writing deliberately.

No new nodes are allocated except the dummy. The problem asks for splicing, and splicing is what makes this O(1) space.

Complexity

O(n + m) time — every node is visited once.

O(1) space. The recursive version below is O(n + m) space because of the call stack.

The recursive version

def mergeTwoLists(self, l1, l2):
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    l2.next = self.mergeTwoLists(l1, l2.next)
    return l2

Shorter and pleasant to read. The base cases handle the leftovers automatically. It is O(n + m) stack space, so it will overflow on long lists — the same trade as 4.9.1.

Where this goes next

• Merge k Sorted Lists — merge many. Either pair them up repeatedly, or keep a heap of the k current heads. 4.9.10.
• Sort List — merge sort on a linked list, using this as its merge step and slow-fast pointers to split.
• Merge Sorted Array — the array version, best done backwards so you do not overwrite unread values.

What the interviewer will push on

"Why a dummy node?" So the first node needs no special case. This is the answer they want, and it generalises to every insert-or-delete linked-list problem.

"What if one list is much longer?" The loop ends when the short one runs out, and the rest is attached in one step. No extra cost.

"Can you do it in O(1) space?" The iterative version already is. The recursion is not.

One thing to volunteer: point out that this is merge sort's merge step, and that linked lists are the one place merge sort needs no extra memory.

Next: 4.9.3 Reorder List — three separate linked-list techniques used one after another in a single problem.