Merge K Sorted Lists

Approach Summary

Use a min-heap of size k storing (value, list_index, node). Extract min, add to result, push next node from that list.

Full Solution & Approach

Merging k sorted lists naively — scan all k heads to find the minimum each time — is O(nk). A min-heap fixes the selection: push the head of every list, then repeatedly extract the minimum node, append it to the result, and push that node's next. The heap always holds at most one node per list, so each extraction is O(log k) and the total is O(n log k), where n is the total number of nodes. A dummy head keeps the result construction uniform. The heap entry must be ordered by value; because the problem guarantees distinct values in the standard version, storing nodes directly works. This is the canonical "merge k sorted streams" pattern — the same heap-of-k-heads idea merges k sorted arrays and powers external sort. Divide-and-conquer pairwise merging is the O(n log k) alternative with O(1) extra heap space.

n total nodes, each pushed and popped once with O(log k) heap work — O(n log k) time. The heap holds at most k heads — O(k) space, plus the output list.

Solution Code

Solution

import heapq

def merge_k_lists(lists):
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = cur = ListNode(0)
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

function mergeKLists(lists) {
  const heap = [];
  const push = (v, i, node) => {
    heap.push([v, i, node]);
    let p = heap.length - 1;
    while (p > 0) {
      const par = Math.floor((p - 1) / 2);
      if (heap[par][0] <= heap[p][0]) break;
      [heap[par], heap[p]] = [heap[p], heap[par]];
      p = par;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]];
        i = s;
      }
    }
    return top;
  };
  for (let i = 0; i < lists.length; i++) {
    if (lists[i]) push(lists[i].val, i, lists[i]);
  }
  const dummy = new ListNode(0);
  let cur = dummy;
  while (heap.length) {
    const [, i, node] = pop();
    cur.next = node;
    cur = cur.next;
    if (node.next) push(node.next.val, i, node.next);
  }
  return dummy.next;
}

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

ListNode* mergeKLists(const vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* head : lists) if (head) heap.push(head);
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        cur->next = node;
        cur = cur->next;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

Edge Cases to Watch

All lists empty — return null
One non-empty list — merge is trivial
Lists of very different lengths — the heap handles them uniformly
Duplicate values across lists — fine for a linked-list merge

How to Recognize This Pattern

Merge k sorted sequences
Heap of k heads

Complexity Analysis

Time Complexity

O(n log k)

Space Complexity

O(k)