36. Merge k Sorted Lists

HardLinked List Heap Sorting

You are given an array lists of k singly linked lists, each sorted in ascending order. Some of the lists may be empty, and lists itself may be empty.

Merge all of them into one sorted linked list and return its head.

Example 1

Input: lists = [[1,5,9],[2,3,10],[4,6]]
Output: [1,2,3,4,5,6,9,10]

Example 2

Input: lists = []
Output: []

Example 3

Input: lists = [[]]
Output: []

Explanation: One list, and it has no nodes.

Constraints

0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= Node.val <= 10^4
Each list is sorted in ascending order, and the total number of nodes is at most 10^4

💡 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