23. Merge K Sorted Lists

Q: Why is O(n log k) better than O(n log n)?

Because k ≤ n always, so log k ≤ log n. If k is much smaller than n (e.g., k = 10 lists with 10,000 nodes each, n = 100,000), O(n log k) ≈ O(n * 3.32) while O(n log n) ≈ O(n * 16.6) — nearly 5× more work.

Q: Can the heap store nodes directly instead of [value, node] pairs?

In principle yes, but in a typed heap (like Java's PriorityQueue), you'd provide a comparator. In JS with a simulated heap, you need the value alongside the node for sorting.

Q: Which approach scales better to distributed systems?

Divide-and-conquer maps naturally to a tree of merge workers (each merging two streams). A central k-way heap creates a single coordination point — potentially a bottleneck. At Citadel's scale, distributed merge trees are the standard architecture.

hardAsked at Citadel

Merging K sorted streams is a critical primitive in market data aggregation — combining order flow from K exchanges into a single time-ordered feed. Citadel uses this as a hard problem to test heap fundamentals, divide-and-conquer thinking, and whether you can argue O(n log k) vs O(nk) with precision.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2026-Q1)— Citadel SWE on-site candidates report Merge K Sorted Lists as a standard hard-round question, often requiring the min-heap approach.
Blind (2025-10)— Citadel SWE threads list Merge K Sorted Lists as a reliable hard-round problem, with interviewers specifically probing O(n log k) complexity reasoning.

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]

Explanation: Three sorted lists merged into one sorted list.

Example 2

Input

lists = []

Output

[]

Explanation: Empty input — return null.

Approaches

1. Min-heap (priority queue)

Push the head of each list into a min-heap. Repeatedly extract the minimum, append it to the result, and push the next node from its list. O(n log k) total.

Time: O(n log k) where n = total nodes, k = number of lists
Space: O(k) heap

// Simulate min-heap with sorted array for interview.
// In production: implement a binary min-heap for true O(log k) operations.
function mergeKLists(lists) {
  const dummy = { val: 0, next: null };
  let tail = dummy;

  // Initialize heap with head of each non-null list
  // [value, node] pairs sorted by value
  const heap = [];
  for (const head of lists) {
    if (head) heap.push([head.val, head]);
  }
  // Sort to establish initial heap order
  heap.sort((a, b) => a[0] - b[0]);

  while (heap.length) {
    const [, node] = heap.shift(); // extract min
    tail.next = node;
    tail = tail.next;
    if (node.next) {
      // Re-insert the next node from this list
      const next = [node.next.val, node.next];
      let lo = 0, hi = heap.length;
      while (lo < hi) { // binary search insertion
        const mid = (lo + hi) >> 1;
        if (heap[mid][0] <= next[0]) lo = mid + 1; else hi = mid;
      }
      heap.splice(lo, 0, next);
    }
  }
  return dummy.next;
}

Tradeoff: True min-heap gives O(log k) per extraction and insertion. The sorted-array simulation above is O(k) per insertion (splice). For a proper O(n log k) solution, implement a binary heap. Always explain the heap approach conceptually and note the JS simulation limitation.

2. Divide and conquer

Repeatedly merge pairs of lists using the O(m+n) two-list merge. After log k rounds, all lists are merged. Total work: O(n log k).

Time: O(n log k)
Space: O(log k) call stack

function mergeKLists(lists) {
  if (!lists.length) return null;

  function mergeTwoLists(l1, l2) {
    const dummy = { val: 0, next: null };
    let tail = dummy;
    while (l1 && l2) {
      if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
      else { tail.next = l2; l2 = l2.next; }
      tail = tail.next;
    }
    tail.next = l1 || l2;
    return dummy.next;
  }

  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      merged.push(mergeTwoLists(lists[i], lists[i + 1] || null));
    }
    lists = merged;
  }
  return lists[0];
}

Tradeoff: Same O(n log k) asymptotic as the heap approach but no heap needed. Easier to implement correctly in JavaScript. The iterative version (while loop pairing adjacent lists) avoids deep recursion. This is often the cleaner interview answer in JS.

Citadel-specific tips

State the complexity argument before coding: 'Naively merging one list at a time is O(nk). With divide-and-conquer or a k-way heap, each node is touched O(log k) times, giving O(n log k). At k = 10,000 exchanges and n = 10^8 total events per day, the difference between O(nk) and O(n log k) is 10,000x.' Citadel will appreciate this quantitative framing. Also ask: 'What if the k lists are live streams, not static arrays?' — the heap approach generalizes directly to streaming; divide-and-conquer does not.

Common mistakes

Using a brute-force collect-all-nodes-then-sort approach — O(n log n) instead of O(n log k), and misses the heap insight.
Not handling null lists in the input (empty lists in the array) — must check if head is null before pushing to the heap.
In divide-and-conquer, forgetting to handle odd-length lists (the last list has no pair) — handle with lists[i+1] || null.
Describing O(n log k) but then implementing O(nk) naive merging — inconsistency is immediately flagged.

Follow-up questions

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

Smallest Range Covering Elements from K Lists (LC 632) — harder heap variant.
How would you handle this if the K lists are live socket streams?
What is the space overhead of the heap approach versus divide-and-conquer?

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 O(n log k) better than O(n log n)?

Because k ≤ n always, so log k ≤ log n. If k is much smaller than n (e.g., k = 10 lists with 10,000 nodes each, n = 100,000), O(n log k) ≈ O(n * 3.32) while O(n log n) ≈ O(n * 16.6) — nearly 5× more work.

Can the heap store nodes directly instead of [value, node] pairs?

In principle yes, but in a typed heap (like Java's PriorityQueue), you'd provide a comparator. In JS with a simulated heap, you need the value alongside the node for sorting.

Which approach scales better to distributed systems?

Divide-and-conquer maps naturally to a tree of merge workers (each merging two streams). A central k-way heap creates a single coordination point — potentially a bottleneck. At Citadel's scale, distributed merge trees are the standard architecture.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →