Merge Two Sorted Lists

The problem

You are given a and b, the first nodes of two linked lists. In each list the values are sorted from smallest to largest, and equal values may sit next to each other. Return the first node of one sorted list that holds every node of both. A node holds a value, val, and a link, next, to the node after it; null stands for an empty list. Either list may be empty, and if both are, return null. You may relink the given nodes or build new ones.

What to write

type ListNode = { val: number; next: ListNode | null };

function solve(a: ListNode | null, b: ListNode | null): ListNode | null

Input
a = {"val":1,"next":{"val":3,"next":null}}
b = {"val":2,"next":null}

Output
{"val":1,"next":{"val":2,"next":{"val":3,"next":null}}}

Input
a = null
b = null

Output
null

Constraints

0–500 nodes in each acyclic sorted list; integer values.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Both lists are already in order, and each can hold 500 nodes. Sorting all the values again would throw that order away and repeat work that is already done. Either list may also be empty, and then the other list is the whole answer.

2. Hint 2: Ask a smaller question

   Lay out 1 → 3 and 2 as two rows of cards. Which card must come first in the answer? Take it away. Which card comes next, and which cards did you have to look at to decide?

3. Hint 3: Name the pattern

   The smallest node not yet merged is always at the front of one of the two lists, so you only ever compare two nodes. The smaller one is attached to the end of the answer by changing a link, with no copying. This is linked list pointer rewiring: the answer is built from the nodes you were given. Read the lesson on linked list pointer rewiring.

4. Hint 4: State the invariant

   The merged list is always sorted, and every node still waiting in a or b is at least as large as the merged list's last node. So the smaller of the two front nodes can always go at the end.

5. Hint 5: Sketch the pseudocode

   Make a placeholder node and call it the end. While both a and b have a node: link the end to the one with the smaller value and move that list to its next node. The linked node becomes the new end. Then link the end to whichever list is left. Return the node after the placeholder.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Append the smaller current node to a dummy-headed output chain. When one list ends, attach the remainder of the other.

The slow way

Collect every value from both lists in an array, sort the array, and build a new list from it. The answer is right, but sorting n + m values takes about (n + m) log(n + m) steps and ignores the order the lists already have. It also creates a new node for every value.

The insight

Because both lists are sorted, the smallest node that is not merged yet is always the first node of one of them. So one comparison decides which node comes next, and attaching it changes one link.

Step by step

1. Start the merged list with a placeholder node in front. A placeholder, often called a dummy node, is an extra node that holds no real value. With it in front, the first real node is attached the same way as every later one: after the current end.
2. While both lists have nodes, attach the smaller front node. The smaller of the two front nodes is the smallest node left, so that node comes next, and the list it came from moves one node forward. On a tie either node may go first.
3. The attached node is the new end of the merged list. The code keeps a marker on the last node of the merged list, because that is where the next node is attached. If the marker stayed where it was, every new node would replace the one attached before.
4. One list has run out: attach all that is left of the other. The nodes that are left are already linked in order, and none is smaller than the end of the merged list, so one link attaches them all. If both lists were empty from the start, that link is null.
5. The merged list starts right after the placeholder. The placeholder only gave the first real node something to be attached to. It is not part of the answer, so the node after it is returned.

The same numbered steps are the comments in each solution.

function solve(a, b) {
  // 1. Start the merged list with a placeholder node in front
  const dummy = { val: 0, next: null };
  let tail = dummy;
  // 2. While both lists have nodes, attach the smaller front node
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    // 3. The attached node is the new end of the merged list
    tail = tail.next;
  }
  // 4. One list has run out: attach all that is left of the other
  tail.next = a || b;
  // 5. The merged list starts right after the placeholder
  return dummy.next;
}

type ListNode = { val: number; next: ListNode | null };
function solve(
  a: ListNode | null,
  b: ListNode | null,
): ListNode | null {
  // 1. Start the merged list with a placeholder node in front
  const dummy: ListNode = { val: 0, next: null };
  let tail = dummy;
  // 2. While both lists have nodes, attach the smaller front node
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    // 3. The attached node is the new end of the merged list
    tail = tail.next!;
  }
  // 4. One list has run out: attach all that is left of the other
  tail.next = a || b;
  // 5. The merged list starts right after the placeholder
  return dummy.next;
}

def solve(a, b):
    # 1. Start the merged list with a placeholder node in front
    dummy = tail = ListNode()
    # 2. While both lists have nodes, attach the smaller front node
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        # 3. The attached node is the new end of the merged list
        tail = tail.next
    # 4. One list has run out: attach all that is left of the other
    tail.next = a or b
    # 5. The merged list starts right after the placeholder
    return dummy.next

Example 1, traced

Input
a = {"val":1,"next":{"val":3,"next":null}}
b = {"val":2,"next":null}

Output
{"val":1,"next":{"val":2,"next":{"val":3,"next":null}}}

Why it works

The merged list is sorted at every moment, and every node still waiting is at least as large as the merged list's last node. Attaching the smaller front node keeps both facts true. When one list runs out, the rest of the other is sorted and large enough, so attaching it whole finishes the merge.

Time and space

Time O(n + m), extra space O(1) extra. Each round of the loop attaches one node, so there are at most n + m rounds for lists of n and m nodes: O(n + m) time. The given nodes are reused. Only the placeholder and a reference to the end are added, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Move the end marker onto each node you attach. If it stays on the placeholder, every node replaces the one attached before it: 1 → 3 and 2 give the single node 3.
• When the loop ends, one list may still hold nodes. Attach them, or they are lost: 1 → 3 and 2 give 1 → 2, without the 3.
• Return the node after the placeholder, not the placeholder. Otherwise the answer starts with an extra node holding 0, and two empty lists give that one node instead of null.

Pattern

Linked list pointer rewiring. Builds on Reverse Linked List.

Keep going