Skip to main content

23. Merge K Sorted Lists

hardAsked at Gusto

Merge k sorted linked lists into one. Gusto asks this as the natural escalation from Merge Two Sorted Lists — they want to see the divide-and-conquer approach or a min-heap, and they care that you recognise the O(Nk) naive solution is unacceptable.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-12)— Reported as a Gusto senior SWE onsite problem paired with Merge Two Sorted Lists earlier in the interview.
  • Blind (2025-10)— Gusto threads cite Merge K Sorted Lists as a hard problem that tests both heap reasoning and divide-and-conquer.

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: All three sorted lists are merged into one globally sorted list.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input — return null.

Approaches

1. Divide and conquer (pairwise merge)

Repeatedly pair lists and merge each pair, halving the number of lists each round. Like a merge-sort tree — O(log k) rounds, each round O(N) total.

Time
O(N log k) where N is total nodes
Space
O(log k) for recursion
function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  return mergeRange(lists, 0, lists.length - 1);
}
function mergeRange(lists, left, right) {
  if (left === right) return lists[left];
  const mid = Math.floor((left + right) / 2);
  const l1 = mergeRange(lists, left, mid);
  const l2 = mergeRange(lists, mid + 1, right);
  return mergeTwoLists(l1, l2);
}
function mergeTwoLists(l1, l2) {
  const dummy = { val: -1, 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;
}

Tradeoff: O(N log k) time, O(log k) stack space. No external heap needed. Builds on the two-list merge as a subroutine — elegant if you already implemented Merge Two Sorted Lists.

2. Min-heap (priority queue)

Push all list heads into a min-heap. Repeatedly extract the minimum, append to result, and push that node's next into the heap.

Time
O(N log k)
Space
O(k) for the heap
// JS has no built-in heap — sketch with sorted array as a stand-in
// In a real interview, use a MinPriorityQueue or implement a heap.
function mergeKLists(lists) {
  // Simulate heap with sorted insertion (educational — real heap preferred)
  let heap = [];
  for (const head of lists) {
    if (head) heap.push(head);
  }
  heap.sort((a, b) => a.val - b.val); // initial heapify
  const dummy = { val: -1, next: null };
  let tail = dummy;
  while (heap.length) {
    const node = heap.shift(); // extract min
    tail.next = node;
    tail = tail.next;
    if (node.next) {
      // insert next and maintain sort (O(k) per step in this sketch)
      const insertIdx = heap.findIndex(n => n.val > node.next.val);
      insertIdx === -1 ? heap.push(node.next) : heap.splice(insertIdx, 0, node.next);
    }
  }
  return dummy.next;
}

Tradeoff: With a proper binary heap: O(N log k) time, O(k) space. The sketch above uses sorted array insertion (O(k) per step = O(Nk) total) — always mention this limitation and that a real heap is needed. In a production JS context, use a library or implement a MinHeap class.

Gusto-specific tips

Lead with the divide-and-conquer approach since it builds directly on Merge Two Sorted Lists (which Gusto may have asked earlier in the same session). Explicitly state why the naive approach — merging one list at a time from left to right — is O(Nk) and unacceptable. If the interviewer asks for the heap approach, note that JS lacks a built-in min-heap and sketch the API you'd want.

Common mistakes

  • Merging lists sequentially left-to-right — O(Nk) time, not O(N log k).
  • Forgetting to handle the empty lists array — return null immediately.
  • In the heap approach, not pushing the next node after extraction — the heap will drain early.
  • Off-by-one in the divide step — ensure left and right boundaries are tracked correctly to avoid infinite recursion.

Follow-up questions

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

  • What if each list is very long (1 million nodes) but k is small (3 lists)? Does your approach change?
  • How would you merge k sorted arrays rather than linked lists?
  • What is the memory usage comparison between divide-and-conquer and heap approaches?

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

Each node is touched once per merge level. There are log k levels (halving k lists each round). Total work = N × log k, not N × log N.

Which approach is better in practice?

Both are O(N log k). Divide-and-conquer avoids external data structures and is cache-friendly. The heap approach is more natural if k changes dynamically (e.g., streaming input).

Does JavaScript have a built-in min-heap?

No. You'd either implement one or use a library. In an interview, describe the heap API you'd use (insert, extractMin) and state the complexity, then implement divide-and-conquer as the code.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →