Skip to main content

24. Merge k Sorted Lists

hardAsked at Freshworks

Merge k sorted linked lists into one — Freshworks frames it directly as merging k per-shard ticket queues into one global SLA-sorted stream.

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 <= 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. Brute force (collect + sort)

Walk every node into an array, sort, then rebuild a list.

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

Tradeoff:

2. Min-heap over k heads

Push all k heads into a min-heap keyed by val. Repeatedly pop the smallest, append it, and push its next. O(N log k).

Time
O(N log k)
Space
O(k)
class MinHeap { /* push/pop by val */ }
function mergeKLists(lists) {
  const h = new MinHeap();
  for (const node of lists) if (node) h.push(node);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (h.size()) {
    const n = h.pop();
    tail.next = n; tail = n;
    if (n.next) h.push(n.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Freshworks-specific tips

Freshworks expects you to name the heap-vs-divide-and-conquer trade-off — both are O(N log k), but the heap version is what their SLA-merge service actually uses because lists arrive online.

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

Practice these live with InterviewChamp.AI →