Skip to main content

24. Merge K Sorted Lists

hardAsked at Gojek

Merge k sorted linked lists into a single sorted linked list and return its head.

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

Problem

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

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 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 and sort

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

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

Tradeoff:

2. Min-heap of heads

Push all list heads into a min-heap keyed by value; pop the smallest, append to the output, and push its next. Total work is N log k where N is total nodes and k is list count.

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

Tradeoff:

Gojek-specific tips

Gojek interviewers expect candidates to default to heap-based merges because regional dispatcher streams arrive partitioned and must reconcile in a single sorted timeline.

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

Practice these live with InterviewChamp.AI →