Skip to main content

29. Merge k Sorted Lists

hardAsked at Mercury

Merge k sorted linked lists into a single sorted list efficiently.

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

Problem

You are given an array of k sorted linked lists. Merge all of them into one ascending sorted linked list and return the head. Total node count is N across all lists.

Constraints

  • 0 <= k <= 10^4
  • 0 <= each list length <= 500
  • -10^4 <= Node.val <= 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-then-sort

Dump every value into an array, sort, then rebuild the linked list.

Time
O(N log N)
Space
O(N)
const vals=[]; for(const h of lists){ let c=h; while(c){ vals.push(c.val); c=c.next;}}
vals.sort((a,b)=>a-b);
const d={next:null}; let p=d; for(const v of vals){ p.next={val:v,next:null}; p=p.next;} return d.next;

Tradeoff:

2. Min-heap of k heads

Push each list head into a min-heap, repeatedly pop the smallest and push its next; result is sorted in O(N log k).

Time
O(N log k)
Space
O(k)
// Sketch using a binary-heap helper:
function mergeKLists(lists) {
  const heap = new MinHeap((a, b) => a.val - b.val);
  for (const head of lists) if (head) heap.push(head);
  const dummy = { next: null };
  let tail = dummy;
  while (heap.size()) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Mercury-specific tips

Mercury uses k-way merge to model end-of-day reconciliation — merging k sorted ACH/wire feeds from multiple correspondent banks into one chronologically posted ledger is the literal job description for their treasury team.

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

Practice these live with InterviewChamp.AI →