Skip to main content

23. Merge K Sorted Lists

hardAsked at Bloomberg

Bloomberg's order-book engine merges price-sorted queues from dozens of exchanges every microsecond — this problem tests whether you can do the same efficiently using a min-heap instead of naive repeated merging.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge all linked lists into one sorted linked list and return it.

Constraints

  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4

Examples

Example 1

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

Explanation: Merging all three sorted lists produces the single sorted output.

Example 2

Input
lists = []
Output
[]

Approaches

1. Brute force

Collect all values, sort them, rebuild a linked list. Simple but wastes the pre-sorted structure.

Time
O(N log N)
Space
O(N)
function mergeKLists(lists) {
  const vals = [];
  for (const head of lists) {
    let node = head;
    while (node) { vals.push(node.val); node = node.next; }
  }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let cur = dummy;
  for (const v of vals) { cur.next = { val: v, next: null }; cur = cur.next; }
  return dummy.next;
}

Tradeoff:

2. Min-heap (priority queue)

Push the head of each list into a min-heap keyed by node value. Each extraction gives the global minimum; push the extracted node's successor. O(N log k) with k = list count.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(item) {
    this.data.push(item);
    this._bubbleUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._siftDown(0); }
    return top;
  }
  size() { return this.data.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p].val <= this.data[i].val) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      let smallest = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l].val < this.data[smallest].val) smallest = l;
      if (r < n && this.data[r].val < this.data[smallest].val) smallest = r;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null };
  let cur = dummy;
  while (heap.size()) {
    const node = heap.pop();
    cur.next = node;
    cur = cur.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff:

Bloomberg-specific tips

Bloomberg grades this problem heavily on complexity analysis — interviewers expect you to name 'O(N log k)' before coding, not after. The real Bloomberg hook is the order-book analogy: each exchange feed is a sorted stream, and latency budgets mean you can't afford the O(N log N) sort. Mention that your heap size stays bounded at k regardless of total node count N.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Merge K Sorted Lists and other Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →