Skip to main content

23. Merge k Sorted Lists

hardAsked at Swiggy

Merge k sorted linked lists into one sorted linked list.

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

Problem

You are given an array of k sorted linked lists. Merge them all into one sorted linked list and return its head.

Constraints

  • 0 <= k <= 10^4
  • 0 <= lists[i].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, sort, rebuild

Dump all values into an array, sort, build a new list.

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

Tradeoff:

2. Min-heap of list heads

Push the head of each list into a min-heap keyed by node value. Pop the smallest, append it to the result, then push its next. Continue until the heap is empty.

Time
O(N log k)
Space
O(k)
function mergeKLists(lists) {
  const heap = [];
  const push = (n) => {
    heap.push(n);
    let i = heap.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (heap[p].val <= heap[i].val) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
  };
  const pop = () => {
    const top = heap[0]; const last = heap.pop();
    if (heap.length) { heap[0] = last; let i = 0; const n = heap.length;
      while (true) { let l = 2*i+1, r = 2*i+2, s = i;
        if (l < n && heap[l].val < heap[s].val) s = l;
        if (r < n && heap[r].val < heap[s].val) s = r;
        if (s === i) break; [heap[s], heap[i]] = [heap[i], heap[s]]; i = s; }
    }
    return top;
  };
  for (const l of lists) if (l) push(l);
  const dummy = { val: 0, next: null }; let curr = dummy;
  while (heap.length) { const n = pop(); curr.next = n; curr = n; if (n.next) push(n.next); }
  curr.next = null;
  return dummy.next;
}

Tradeoff:

Swiggy-specific tips

Swiggy uses k-way merge as a stand-in for merging sorted ETA streams from multiple courier hubs; the heap approach demonstrates fluency in real-time dispatch logic.

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

Practice these live with InterviewChamp.AI →