Skip to main content

23. Merge k Sorted Lists

hardAsked at Robinhood

Given an array of k sorted linked lists, merge them into one sorted list. Robinhood asks this as the canonical heap-of-streams problem — it maps directly to merging k sorted streams of trades or price-feed events.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports list Merge k Sorted Lists as a recurring hard round.
  • Blind (2025-12)— Robinhood backend trip reports describe heap-of-streams patterns as a thematic favorite.

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

Approaches

1. Sequential pairwise merge

Repeatedly merge two lists at a time using a standard two-list merge.

Time
O(N * k) where N is total nodes
Space
O(1)
function mergeTwoLists(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 mergeKListsSeq(lists) {
  let result = null;
  for (const list of lists) result = mergeTwoLists(result, list);
  return result;
}

Tradeoff: O(N * k) — each node is re-walked once per pairwise merge. Mention it, then move to divide-and-conquer or heap.

2. Min-heap of list heads (optimal)

Push all list heads into a min-heap. Pop the smallest, append to result, push its next (if any).

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

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.size()) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff: O(N log k) — each of N nodes is pushed and popped once, each heap op is O(log k). Standard heap-of-streams pattern. Robinhood interviewers expect this answer.

3. Divide and conquer pairwise merge

Recursively split the list of lists in half, merge each half, merge the two halves.

Time
O(N log k)
Space
O(log k) recursion
function mergeTwoLists(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 merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const a = lists[i];
      const b = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwoLists(a, b));
    }
    lists = merged;
  }
  return lists[0];
}

Tradeoff: Same O(N log k). Cleaner without heap implementation. Use when you don't have a heap class memorized.

Robinhood-specific tips

Robinhood expects O(N log k). Heap is the canonical answer; divide-and-conquer pairwise merge is the fallback if you don't want to write a heap from scratch under pressure. Articulate the cost split: 'each node is touched once for insert, once for pop, each at O(log k).' Don't fall back to the naive pairwise sequential merge — it's O(N * k) and shows you didn't think about the k dimension.

Common mistakes

  • Forgetting to push node.next after popping — the heap drains and result is incomplete.
  • Pushing null heads into the heap when a list is empty — gives undefined.val on comparison.
  • Not setting tail.next = null at the end — leaves a dangling reference to the last popped node's old next.

Follow-up questions

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

  • Merge k sorted streams (no length known) — same heap pattern with lazy reads.
  • Smallest Range Covering Elements from K Lists (LC 632) — similar heap shape.
  • Find K Pairs with Smallest Sums (LC 373) — heap of (i, j) pair indices.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap vs divide-and-conquer — which is preferred?

Same asymptotic. Heap is more interview-classic and generalizes to streams. Divide-and-conquer is easier to code without a heap class. Pick whichever you can write bug-free.

Why O(N log k) and not O(N log N)?

Because at any moment the heap contains at most k elements (one per list). Each insert/pop is log k, not log N.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →