Skip to main content

25. Merge k Sorted Lists

hardAsked at Ramp

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 linked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

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. Brute force collect-and-sort

Push every node value into an array, sort, rebuild a linked list.

Time
O(N log N)
Space
O(N)
function mergeKLists(lists) {
  const vals = [];
  for (const head of lists) { let c = head; while (c) { vals.push(c.val); c = c.next; } }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, 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 list heads

Push the head of each list into a min-heap keyed by value. Pop the smallest, append it to the result, push its next. Each node enters and leaves the heap once.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(x) { this.h.push(x); this._up(this.h.length - 1); }
  pop() { const top = this.h[0], last = this.h.pop(); if (this.h.length) { this.h[0] = last; this._down(0); } return top; }
  size() { return this.h.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.h[p].val <= this.h[i].val) break; [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; } }
  _down(i) { const n = this.h.length; while (true) { let l = 2*i+1, r = 2*i+2, s = i; if (l < n && this.h[l].val < this.h[s].val) s = l; if (r < n && this.h[r].val < this.h[s].val) s = r; if (s === i) break; [this.h[s], this.h[i]] = [this.h[i], this.h[s]]; i = s; } }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null }; let cur = dummy;
  while (heap.size()) {
    const node = heap.pop();
    cur.next = node; cur = node;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff:

Ramp-specific tips

Ramp uses k-way merging in their AP automation when reconciling sorted streams of bank-feed events from many institutions — the heap pattern is canonical and you'll be asked to defend log-k versus k tradeoffs.

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

Practice these live with InterviewChamp.AI →