Skip to main content

26. Merge k Sorted Lists

hardAsked at Wise

Merge k sorted linked lists into one — Wise reframes it as collapsing k ordered per-corridor settlement streams into a single FIFO ledger.

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

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.

Constraints

  • 0 <= k <= 10^4
  • 0 <= total nodes <= 10^4
  • -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. Concatenate and sort

Dump every node value into an array, sort it, rebuild a list.

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

Tradeoff:

2. Min-heap of head pointers

Push the head of each list into a min-heap keyed by value; pop the min, append it, then push its next. Each node enters and leaves the heap once.

Time
O(n log k)
Space
O(k)
function mergeKLists(lists){
  const heap = [];
  const push = node => {
    heap.push(node);
    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;
      while (true){
        const l = i*2+1, r = i*2+2;
        let m = i;
        if (l < heap.length && heap[l].val < heap[m].val) m = l;
        if (r < heap.length && heap[r].val < heap[m].val) m = r;
        if (m === i) break;
        [heap[m], heap[i]] = [heap[i], heap[m]];
        i = m;
      }
    }
    return top;
  };
  for (const h of lists) if (h) push(h);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.length){
    const n = pop();
    tail.next = n; tail = n;
    if (n.next) push(n.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Wise-specific tips

Wise grades the heap solution closely because their multi-corridor settlement merger runs the same n log k merge over per-currency ordered streams every cycle.

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

Practice these live with InterviewChamp.AI →