Skip to main content

24. Merge k Sorted Lists

hardAsked at Yelp

Merge k sorted linked lists into one — Yelp uses min-heap-of-heads to test whether candidates can scale a streaming merge to fanned-in review-event shards.

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 linked-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. Concat and sort

Flatten every list into one array, sort, and rebuild.

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

Tradeoff:

2. Min-heap of heads

Maintain a min-heap keyed on each list's head value; pop the smallest, append it, push its next. Repeat until empty.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(x) { this.h.push(x); this.h.sort((a,b) => a.val - b.val); }
  pop() { return this.h.shift(); }
  size() { return this.h.length; }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { next: null };
  let cur = dummy;
  while (heap.size()) {
    const node = heap.pop();
    cur.next = node; cur = node;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff:

Yelp-specific tips

Yelp will pivot to review fraud — be ready to discuss how a k-way merge over per-shard sorted-by-time review streams supports a single chronological feed for fraud anomaly scoring.

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

Practice these live with InterviewChamp.AI →