Merge K Sorted Lists

The problem

lists is an array of linked lists. Each entry is the first node of a list whose values are sorted from smallest to largest, or null for an empty list. A node holds a value, val, and a link, next, to the node after it. Return the first node of one sorted list that holds every node of all the lists, with equal values all kept. If lists is empty, or holds only empty lists, return null. You may relink the given nodes or build new ones.

What to write

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

function solve(lists: (ListNode | null)[]): ListNode | null

Input
lists = [{"val":1,"next":{"val":4,"next":{"val":5,"next":null}}},{"val":1,"next":{"val":3,"next":{"val":4,"next":null}}},{"val":2,"next":{"val":6,"next":null}}]

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

Input
lists = []

Output
null

Constraints

Nodes use {val, next}; the combined node count is at most 10000.

Hints

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

1. Hint 1: Use the constraints

   Every list is already sorted, so collecting all the values and sorting them again throws that work away. Two sorted lists can be merged in a single pass over their nodes. With up to 10,000 nodes in many lists, the question is how to avoid walking the same nodes again and again.

2. Hint 2: Ask a smaller question

   Suppose you merge four lists of 100 nodes one at a time: the first with the second, the result with the third, then with the fourth. In how many merges do the nodes of the first list take part? And those of the fourth? Is there an order of merging that treats the lists more evenly?

3. Hint 3: Name the pattern

   The answer is built from the nodes you were given, by changing where their next links point: that is linked list pointer rewiring, and merging two sorted lists is the tool. The new part is the order. Merge the lists in pairs, then merge the results in pairs, until one list is left. Read the lesson on linked list pointer rewiring.

4. Hint 4: State the invariant

   Call each position of lists a slot. At the start of a round the lists still in play sit a fixed gap apart, at first in every slot. Each is sorted and holds every node of the lists merged into it. Merging neighbors among them about halves their number and doubles the gap.

5. Hint 5: Sketch the pseudocode

   If there are no lists, return null. Set gap to 1. While gap is less than the number of lists: for i = 0, then two gaps on, four gaps on and so on, while slot i + gap exists, slot i becomes the merge of slots i and i + gap. Then double gap. Return slot 0.

Solution

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

Approach

Merge pairs of lists in rounds, doubling the group size each round. Each node participates in at most log k merges, rounded up.

The slow way

Merge the lists one at a time into a growing result: the first with the second, the result with the third, and so on. It is correct, but the nodes merged early can be walked again in every later merge. For 1,000 lists of 10 nodes each, one run linked nodes about 5 million times, against fewer than 100,000 times for the method below.

The insight

A merge of two lists walks each of their nodes about once. So pair the lists up and merge each pair, then pair up the results and merge again. Every round walks each node at most once and halves the number of lists, so k lists need only about log k rounds, where log k is the number of times k can be halved.

Step by step

1. Merge two sorted lists: keep linking the smaller of two front nodes. This is the merge of two sorted lists. A placeholder node stands in front, so the first real node is linked like every other, and the smaller front node is always the smallest node not yet linked.
2. One list ran out: attach the rest of the other one. The loop stops as soon as one list is empty. What is left of the other list is already sorted and no smaller than everything linked so far, so one link attaches all of it.
3. No lists at all means an empty result. With no lists there is no first slot to return. An empty list is written as null, so null is the answer.
4. Merge in rounds, pairing lists one gap apart; the gap starts at 1. A slot is one position of lists. Partners are two slots whose lists get merged, and the gap is the distance between them. With a gap of 1 they are neighbors: slots 0 and 1, then 2 and 3.
5. Merge each list with its partner and keep the result in its slot. The merged list goes back into the left partner's slot, and the right partner's slot is not read again. A list whose partner would lie past the end of the array waits for a later round.
6. Double the gap: the merged lists now sit twice as far apart. After a round, the lists still in play are two gaps apart: slot 0, two gaps on, four gaps on and so on. Doubling the gap lets the next round pair them up.
7. The first slot now holds every list merged into one. Slot 0 is a left partner in every round, so it is never used up. When the gap reaches the number of lists, no slot has a partner any more and slot 0 holds everything.

The same numbered steps are the comments in each solution.

function solve(lists) {
  // 1. Merge two sorted lists: keep linking the smaller of two front nodes
  function merge(a, b) {
    const d = { val: 0, next: null };
    let t = d;
    while (a && b) {
      if (a.val <= b.val) {
        t.next = a;
        a = a.next;
      } else {
        t.next = b;
        b = b.next;
      }
      t = t.next;
    }
    // 2. One list ran out: attach the rest of the other one
    t.next = a ?? b;
    return d.next;
  }
  // 3. No lists at all means an empty result
  if (!lists.length) return null;
  // 4. Merge in rounds, pairing lists one gap apart; the gap starts at 1
  let step = 1;
  while (step < lists.length) {
    // 5. Merge each list with its partner and keep the result in its slot
    for (let i = 0; i + step < lists.length; i += 2 * step)
      lists[i] = merge(lists[i], lists[i + step]);
    // 6. Double the gap: the merged lists now sit twice as far apart
    step *= 2;
  }
  // 7. The first slot now holds every list merged into one
  return lists[0];
}

type ListNode = { val: number; next: ListNode | null };
function solve(lists: (ListNode | null)[]): ListNode | null {
  // 1. Merge two sorted lists: keep linking the smaller of two front nodes
  function merge(a: ListNode | null, b: ListNode | null): ListNode | null {
    const d: ListNode = { val: 0, next: null };
    let t = d;
    while (a && b) {
      if (a.val <= b.val) {
        t.next = a;
        a = a.next;
      } else {
        t.next = b;
        b = b.next;
      }
      t = t.next;
    }
    // 2. One list ran out: attach the rest of the other one
    t.next = a ?? b;
    return d.next;
  }
  // 3. No lists at all means an empty result
  if (!lists.length) return null;
  // 4. Merge in rounds, pairing lists one gap apart; the gap starts at 1
  let step = 1;
  while (step < lists.length) {
    // 5. Merge each list with its partner and keep the result in its slot
    for (let i = 0; i + step < lists.length; i += 2 * step)
      lists[i] = merge(lists[i], lists[i + step]);
    // 6. Double the gap: the merged lists now sit twice as far apart
    step *= 2;
  }
  // 7. The first slot now holds every list merged into one
  return lists[0];
}

def solve(lists):
    # 1. Merge two sorted lists: keep linking the smaller of two front nodes
    def merge(a, b):
        dummy = tail = ListNode()
        while a and b:
            if a.val <= b.val:
                tail.next = a
                a = a.next
            else:
                tail.next = b
                b = b.next
            tail = tail.next
        # 2. One list ran out: attach the rest of the other one
        tail.next = a or b
        return dummy.next

    # 3. No lists at all means an empty result
    if not lists:
        return None
    # 4. Merge in rounds, pairing lists one gap apart; the gap starts at 1
    step = 1
    while step < len(lists):
        # 5. Merge each list with its partner and keep the result in its slot
        for i in range(0, len(lists) - step, 2 * step):
            lists[i] = merge(lists[i], lists[i + step])
        # 6. Double the gap: the merged lists now sit twice as far apart
        step *= 2
    # 7. The first slot now holds every list merged into one
    return lists[0]

Example 1, traced

Input
lists = [{"val":1,"next":{"val":4,"next":{"val":5,"next":null}}},{"val":1,"next":{"val":3,"next":{"val":4,"next":null}}},{"val":2,"next":{"val":6,"next":null}}]

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

Why it works

A merge of two sorted lists gives a sorted list that holds every node of both. At the start of each round, the slots one gap apart hold sorted lists that together contain every node. A round merges them two by two and doubles the gap, so that stays true, and when a single list is left it is sorted and complete.

Time and space

Time O(N log k), extra space O(1) auxiliary; mutates list array. Each round walks each of the N nodes at most once, and the lists still in play halve every round, so k lists take about log k rounds: O(N log k) time. Nodes are relinked and the slots of lists reused: O(1) extra space, and lists is changed.

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

• When one list runs out, attach what is left of the other. Without that link the leftover nodes are lost: the first example comes back without its last two nodes, 5 and 6.
• Inside a round, move on by two gaps, not one. Moving by one gap merges lists that already share nodes. On the first example the node holding 2 ends up linked to itself, and the merge never ends.
• Check for an empty array before returning the first slot. Without the check, the second example reads a slot that does not exist: Python stops with an error and JavaScript returns undefined instead of null.

Pattern

Linked list pointer rewiring. Builds on Merge Two Sorted Lists.

Keep going