Skip to main content

23. Merge k Sorted Lists

hardAsked at Google

Given k sorted linked lists, merge them into one sorted linked list. Google asks this to see whether you reach for a min-heap, can articulate the n log k vs nk tradeoff, and know how to compare two linked-list nodes inside a priority queue.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports consistently include this as a 45-minute hard.
  • Blind (2025-11)— Recurring in Google staff-IC interview reports as 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 then sort

Dump every value into one array, sort it, rebuild the 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 — that's why it's worse than the heap approach. Useful to mention so the interviewer knows you noticed the structure.

2. Min-heap of list heads (optimal)

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

Time
O(N log k)
Space
O(k)
// MinHeap helper for ListNodes
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-input invariant: at any moment the heap contains exactly one head from each not-yet-exhausted list, so the pop is provably the global minimum.

3. Divide and conquer (alternative optimal)

Pair up lists and merge two-at-a-time, recursively halving until one remains.

Time
O(N log k)
Space
O(log k) recursion
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 the heap but constant-factor faster in practice (no heap bookkeeping). Often the cleanest answer to whiteboard.

Google-specific tips

Google interviewers want you to explicitly compare the heap version's O(N log k) against the naive concatenate-and-sort O(N log N). When the sum of list lengths is N and you have k lists, log k can be dramatically smaller than log N. The interviewer is grading whether you can articulate why preserving the sorted invariant matters.

Common mistakes

  • Forgetting the null-check when pushing list heads — empty lists in the input crash the heap insert.
  • Implementing the heap with the wrong comparator (comparing by reference instead of by .val).
  • Concatenating all values into an array and re-sorting — works but throws away the input invariant.

Follow-up questions

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

  • What if the lists are streams of unknown length? (Heap-based approach still works; concat doesn't.)
  • What if you needed to merge k sorted arrays instead of lists? (Same heap pattern.)
  • How would you parallelize this across machines?

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 from each list). Each push/pop is O(log k), and we do exactly N total operations.

Divide-and-conquer or heap — which does Google prefer?

Both score the same on correctness + complexity. Divide-and-conquer is often the cleaner whiteboard solution because it doesn't require implementing a heap from scratch. Pick whichever you can write bug-free under pressure.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →