Skip to main content

25. Merge k Sorted Lists

hardAsked at MercadoLibre

Merge k sorted linked lists into one sorted list efficiently.

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 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. Collect & sort

Dump every node value into one array, sort, then rebuild a single linked list.

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

Tradeoff:

2. Min-heap of heads

Push the head of every list into a min-heap keyed by value. Pop the smallest, append to the output, and push its next pointer.

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 && heap[(i-1)>>1].val > heap[i].val) { [heap[i], heap[(i-1)>>1]] = [heap[(i-1)>>1], heap[i]]; i = (i-1)>>1; } };
  const pop = () => { const t = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; while (true) { const l = 2*i+1, r = 2*i+2; let s = i; if (l<heap.length&&heap[l].val<heap[s].val) s = l; if (r<heap.length&&heap[r].val<heap[s].val) s = r; if (s===i) break; [heap[i], heap[s]] = [heap[s], heap[i]]; i = s; } } return t; };
  for (const l of lists) if (l) push(l);
  const dummy = { next: null }; let cur = dummy;
  while (heap.length) { const n = pop(); cur.next = n; cur = n; if (n.next) push(n.next); }
  cur.next = null;
  return dummy.next;
}

Tradeoff:

MercadoLibre-specific tips

MercadoLibre logistics teams ask this because courier-feed aggregation works the same way — k sorted ETA streams from regional carriers are merged into a single delivery timeline by min-heap.

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

Practice these live with InterviewChamp.AI →