Skip to main content

26. Merge k Sorted Lists

hardAsked at Klarna

Merge k sorted linked lists into one sorted list.

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

Problem

You are given an array of k linked-lists 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. Concatenate then sort

Dump every node into one array, sort, then rebuild the list.

Time
O(N log N)
Space
O(N)
function mergeKLists(lists) {
  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 = { next: null };
  let tail = dummy;
  for (const v of vals) { tail = tail.next = { val: v, next: null }; }
  return dummy.next;
}

Tradeoff:

2. Min-heap of head pointers

Push the head of every list into a min-heap keyed by value. Pop the smallest, append it to the output, then push its next pointer. 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) { const l = 2*i+1, r = 2*i+2; let m = i; if (l < n && this.h[l].val < this.h[m].val) m = l; if (r < n && this.h[r].val < this.h[m].val) m = r; if (m === i) break; [this.h[m], this.h[i]] = [this.h[i], this.h[m]]; i = m; } }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const l of lists) if (l) heap.push(l);
  const dummy = { next: null };
  let tail = dummy;
  while (heap.size()) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Klarna-specific tips

Klarna's merchant-settlement service literally runs a k-way heap merge across per-merchant payout streams; they grade hard on whether you keep the heap size bounded at k rather than letting it grow to N.

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

Practice these live with InterviewChamp.AI →