Skip to main content

23. Merge k Sorted Lists

hardAsked at Revolut

Merge k sorted linked lists via a min-heap, a Revolut hard-screen that mirrors fan-in merging of k pre-sorted FX-rate streams into a single ordered tape.

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

Problem

Given an array of k linked lists, each sorted ascending, merge all into one sorted linked list and return its head. Target O(N log k) where N is total nodes.

Constraints

  • k == lists.length
  • 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. Concat then sort

Collect all values into one array, sort, rebuild a list.

Time
O(N log N)
Space
O(N)
const arr = []; for (const l of lists){ let c=l; while(c){ arr.push(c.val); c=c.next; } }
arr.sort((a,b)=>a-b);
// rebuild list

Tradeoff:

2. Min-heap of head pointers

Push each list head into a min-heap by value; repeatedly pop the smallest and push its next. O(N log k).

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

Tradeoff:

Revolut-specific tips

Revolut graders will ask you to compare heap-merge vs divide-and-conquer pairwise merge — they want you to justify O(N log k) using the heap-depth argument from a real k-way FX-feed merger.

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

Practice these live with InterviewChamp.AI →