Skip to main content

23. Merge K Sorted Lists

hardAsked at Akamai

Merge K sorted linked lists into one sorted list efficiently. Akamai considers this a flagship problem — merging sorted access logs from thousands of geographically distributed edge servers into a single time-ordered stream is a production use case that maps directly to this algorithm.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Multiple Akamai senior SWE reports list Merge K Sorted Lists as a defining hard-level question in onsite algorithm rounds.
  • Blind (2025-11)— Akamai threads confirm this is asked with explicit discussion of the min-heap vs. divide-and-conquer trade-off.

Problem

You are given an array of k linked 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: All three lists merged and sorted.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input returns empty list.

Approaches

1. Min-heap (priority queue)

Push the head of each non-null list into a min-heap keyed by node value. Repeatedly extract the minimum, attach it to the result, and push the extracted node's next (if non-null). JavaScript requires a manual min-heap.

Time
O(N log k)
Space
O(k)
class MinHeap {
  constructor() { this.data = []; }
  push(node) {
    this.data.push(node);
    this._bubbleUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._sinkDown(0); }
    return top;
  }
  get size() { return this.data.length; }
  _bubbleUp(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;
    }
  }
  _sinkDown(i) {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.data[l].val < this.data[smallest].val) smallest = l;
      if (r < n && this.data[r].val < this.data[smallest].val) smallest = r;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}
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 > 0) {
    const node = heap.pop();
    tail.next = node;
    tail = tail.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) time where N is total nodes and k is list count. O(k) heap space. The heap always holds at most k elements. This is the optimal streaming solution — preferred when k is large and lists arrive lazily.

2. Divide and conquer (pair-wise merge)

Merge lists in pairs repeatedly until one sorted list remains. Each pass halves the number of lists. O(log k) passes, each O(N) total work.

Time
O(N log k)
Space
O(log k) recursion
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;
}
function mergeKLists(lists) {
  if (!lists.length) return null;
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

Tradeoff: Same O(N log k) complexity. More cache-friendly and avoids the heap overhead. Simpler code if you already have mergeTwoLists. Preferred when all data is available upfront.

Akamai-specific tips

Name both approaches and their trade-off explicitly: 'The heap approach is optimal for streaming — the heap holds O(k) nodes at any time, so it works even when list lengths are unbounded. Divide-and-conquer requires all list heads upfront but avoids heap overhead and is simpler to implement.' At Akamai, 'at 10^9 log lines from 10,000 edge servers, the heap approach processes in O(N log k) time with O(k) memory — the only feasible approach at scale.' This framing earns high marks.

Common mistakes

  • Not pushing node.next after extracting from the heap — the next element of each list is never processed.
  • Initializing the heap with all N nodes instead of just k heads — O(N) space instead of O(k), and unnecessary upfront work.
  • Forgetting to handle empty lists or null heads when initializing — causes null-pointer errors on pop.

Follow-up questions

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

  • What if lists are streams (infinite length) — how does the heap approach handle this?
  • Smallest Range Covering Elements from K Lists (LC 632) — find the smallest range containing at least one element from each list.
  • How would you parallelize the merge across multiple machines in a distributed setting?

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 O(N log k) and not O(N log N)?

The heap contains at most k elements at any time. Each push/pop is O(log k), not O(log N). We do N such operations, giving O(N log k). Since k <= N, this is always at least as good as O(N log N).

Why is divide-and-conquer also O(N log k)?

There are log k rounds of merging. In each round, every node is processed exactly once across all merges — O(N) total per round. Total: O(N log k).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →