Skip to main content

26. Merge k Sorted Lists

hardAsked at Coupang

Merge k sorted linked lists into one sorted list, mirroring how Coupang's same-day delivery routing merges sorted dispatch streams from k regional warehouses during peak-event throughput.

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 the lists into one sorted linked list and return it.

Constraints

  • k == lists.length
  • 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]

Example 2

Input
lists=[]
Output
[]

Approaches

1. Collect, sort, rebuild

Push all values into one array, sort, rebuild a list.

Time
O(N log N)
Space
O(N)
const all = [];
for (const head of lists) for (let n = head; n; n = n.next) all.push(n.val);
all.sort((a, b) => a - b);
// rebuild a linked list from all

Tradeoff:

2. Min-heap of list heads

Push the head of each list into a min-heap; repeatedly pop the smallest, append to the result, push its next.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(x) {
    this.h.push(x);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p].val <= this.h[i].val) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
    }
  }
  pop() {
    const top = this.h[0], last = this.h.pop();
    if (this.h.length) { this.h[0] = last; let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2; let m = i;
        if (l < this.h.length && this.h[l].val < this.h[m].val) m = l;
        if (r < this.h.length && this.h[r].val < this.h[m].val) m = r;
        if (m === i) break;
        [this.h[m], this.h[i]] = [this.h[i], this.h[m]]; i = m;
      }
    }
    return top;
  }
  get size() { return this.h.length; }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const node of lists) if (node) heap.push(node);
  const dummy = { val: 0, next: null }; let cur = dummy;
  while (heap.size) {
    const top = heap.pop();
    cur.next = top; cur = cur.next;
    if (top.next) heap.push(top.next);
  }
  return dummy.next;
}

Tradeoff:

Coupang-specific tips

Coupang's same-day delivery routing merges sorted dispatch streams from k regional warehouses during peak-event throughput; the min-heap O(N log k) pattern is the canonical fan-in merge their dispatcher relies on.

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 Coupang interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →