Skip to main content

23. Merge K Sorted Lists

hardAsked at Airbnb

Combine k sorted ranking feeds into one unified result — Airbnb's search infrastructure merges sorted candidate lists from neighborhood, price, and availability shards into a single ranked page of listings.

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 it.

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order
  • The sum of lists[i].length will not exceed 10^4

Examples

Example 1

Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]

Explanation: All three lists are merged into a single sorted linked list.

Example 2

Input
lists = []
Output
[]

Approaches

1. Brute force (collect and sort)

Collect all node values into an array, sort, then rebuild a linked list. Simple but ignores the sorted structure.

Time
O(N log N)
Space
O(N)
function mergeKLists(lists) {
  const vals = [];
  for (const head of lists) {
    let cur = head;
    while (cur) { vals.push(cur.val); cur = cur.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 (priority queue)

Push the head of each list into a min-heap. Repeatedly extract the minimum, append to result, and push that node's next. O(N log k) — optimal for k lists with N total nodes.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  push(node) {
    this.h.push(node);
    let i = this.h.length - 1;
    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;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < this.h.length && this.h[l].val < this.h[s].val) s = l;
        if (r < this.h.length && 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;
      }
    }
    return top;
  }
  size() { return this.h.length; }
}

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 = cur.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff:

Airbnb-specific tips

Airbnb frames this as merging sorted result streams from distributed search shards. The heap approach is the expected answer — articulate why it is O(N log k) rather than O(N log N): you never fully sort, you just maintain a k-element heap. Also be ready with the divide-and-conquer merge-pairs alternative, which achieves the same complexity with O(1) extra space per merge level.

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

Practice these live with InterviewChamp.AI →