Skip to main content

23. Merge k Sorted Lists

hardAsked at Uber

Merge k sorted linked lists into one sorted list. Uber asks this to test whether you reach for the min-heap (or divide-and-conquer pairwise merge) and can articulate why N log k beats N log N.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4/L5 onsite reports consistently include this as a heap or D&C hard.
  • Levels.fyi (2026-Q1)— Uber backend onsite reports list this for the systems-flavored coding round.

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
  • 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]

Example 2

Input
lists = []
Output
[]

Example 3

Input
lists = [[]]
Output
[]

Approaches

1. Concatenate and sort

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

Time
O(N log N)
Space
O(N)
function mergeKListsSort(lists) {
  const all = [];
  for (const head of lists) {
    let node = head;
    while (node) { all.push(node.val); node = node.next; }
  }
  all.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  for (const v of all) { tail.next = { val: v, next: null }; tail = tail.next; }
  return dummy.next;
}

Tradeoff: Throws away the sorted-input invariant. Mention out loud, then pivot — Uber wants to see you spot the wasted structure.

2. Min-heap of list heads (optimal)

Push each list head into a min-heap. Pop the smallest, append, push its next.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(node) {
    this.data.push(node);
    let i = this.data.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p].val <= this.data[i].val) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  pop() {
    if (!this.data.length) return null;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      let i = 0;
      while (true) {
        let l = 2 * i + 1, r = 2 * i + 2, best = i;
        if (l < this.data.length && this.data[l].val < this.data[best].val) best = l;
        if (r < this.data.length && this.data[r].val < this.data[best].val) best = r;
        if (best === i) break;
        [this.data[best], this.data[i]] = [this.data[i], this.data[best]];
        i = best;
      }
    }
    return top;
  }
}

function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.data.length) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff: Preserves the sorted invariant — heap holds one head per not-yet-exhausted list. Each push/pop is O(log k) and there are O(N) of them.

3. Divide and conquer pairwise merge

Merge lists pairwise, halving k each round, until one list remains.

Time
O(N log k)
Space
O(log k) recursion or O(1) iterative
function mergeTwo(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

function mergeKListsDC(lists) {
  if (!lists.length) return null;
  while (lists.length > 1) {
    const next = [];
    for (let i = 0; i < lists.length; i += 2) {
      next.push(mergeTwo(lists[i], lists[i + 1] || null));
    }
    lists = next;
  }
  return lists[0];
}

Tradeoff: Same asymptotic complexity as heap, often faster in practice due to no heap bookkeeping. Cleaner to whiteboard if you've already implemented mergeTwo for LC 21.

Uber-specific tips

Uber's bar on this is explicit complexity narration: 'N total nodes, k lists, heap holds at most k items, push/pop is log k, so total work is N log k.' If you reach for the merge-and-sort answer without naming the cost, that's a flag. Always say why log k matters versus log N.

Common mistakes

  • Forgetting to null-check empty input lists before pushing into the heap.
  • Using a max-heap by accident, or comparing by reference instead of by .val.
  • Concatenating and sorting without acknowledging it discards the sorted-input structure.

Follow-up questions

An interviewer at Uber may pivot to one of these next:

  • What if the lists are unbounded streams? (Heap still works; concat doesn't.)
  • What if you needed to merge k sorted arrays? (Same heap pattern with index pointers.)
  • How would you parallelize across machines? (D&C maps naturally to a reduce.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the heap O(N log k) and not O(N log N)?

The heap only ever holds at most k elements (one head per list). Each push/pop is O(log k), and there are O(N) total operations.

Heap or divide-and-conquer — which does Uber prefer?

Both pass on correctness and complexity. D&C is often cleaner to whiteboard because it doesn't require implementing a heap from scratch. Pick whichever you can write bug-free under pressure.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Merge k Sorted Lists and other Uber interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →