Merge k Sorted Lists

HardLinked List Heap Sorting

A distributed database spreads one table across k shards. For a query, every shard returns the IDs of its matching rows as a singly linked list sorted in ascending order, and a coordinator has to combine them into one sorted list. A shard with no matches returns an empty list, and the coordinator may receive no lists at all.

Given the array lists of shard results, merge all of their nodes into a single ascending linked list and return its head.

Example 1

Input: lists = [[3,8,12],[1,9],[4,5,20]]
Output: [1,3,4,5,8,9,12,20]

Example 2

Input: lists = [[],[6,6],[]]
Output: [6,6]

Explanation: Empty results contribute nothing, and both copies of the repeated ID are kept.

Example 3

Input: lists = [[-10,0],[-5]]
Output: [-10,-5,0]

Constraints

lists holds between 0 and 10^4 linked lists.
Each list has at most 500 nodes, and all lists together have at most 10^4 nodes.
Node values are integers from -10^4 to 10^4.
Every list is sorted in ascending order.

💡 Hint 1

Merging the lists one after another into a growing result works, but the early nodes get rescanned about k times.

💡 Hint 2

The next node of the answer is always the smallest among the current heads of the k lists. Which structure returns the minimum of k items quickly?

💡 Hint 3

Alternatively, merge the lists in pairs, then merge the results in pairs, like the merge step of merge sort.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Let N be the total number of nodes. Two standard ways reach O(N log k):

Min-heap: push the head of every non-empty list into a priority queue keyed by value. Repeatedly pop the smallest node, append it to the result, and push its next if there is one. The heap never holds more than k nodes, so each of the N pops and pushes costs O(log k). This is the Java solution.
Divide and conquer: merge lists 0 and 1, 2 and 3, and so on, halving the number of lists each round with the ordinary two-list merge. There are about log₂ k rounds and each touches every node once. JavaScript has no built-in priority queue, so the JS solution uses this version.

Merging the lists one by one into a single result would instead cost O(N · k).

Time O(N log k)Space O(k)

function mergeKLists(lists) {
  const mergeTwo = (a, b) => {
    const dummy = new ListNode(0);
    let tail = dummy;
    while (a && b) {
      if (a.val <= b.val) {
        tail.next = a;
        a = a.next;
      } else {
        tail.next = b;
        b = b.next;
      }
      tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
  };
  if (!lists.length) return null;
  let current = lists;
  while (current.length > 1) {
    const next = [];
    for (let i = 0; i < current.length; i += 2) {
      next.push(i + 1 < current.length ? mergeTwo(current[i], current[i + 1]) : current[i]);
    }
    current = next;
  }
  return current[0];
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) if (head != null) heap.add(head);
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            if (node.next != null) heap.add(node.next);
        }
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
function mergeKLists(lists) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit