Skip to main content

23. Merge K Sorted Lists

hardAsked at Anduril

Merge k sorted linked lists into one sorted list efficiently. Anduril asks this hard problem to test whether you can design an O(n log k) solution using a min-heap or divide-and-conquer — skills that translate directly to merging ordered event streams from multiple autonomous subsystems in real time.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-12)— Mentioned in Anduril senior SWE onsite reports as a hard question testing heap and divide-and-conquer knowledge.
  • Blind (2025-10)— Anduril senior engineering threads cite Merge K Sorted Lists as a high-signal hard problem for systems-focused roles.

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 lists merged in sorted order.

Example 2

Input
lists = []
Output
[]

Explanation: No lists to merge.

Approaches

1. Divide and conquer (pairwise merge)

Merge lists in pairs repeatedly until one list remains. Like merge sort: O(log k) rounds, each round touches all n elements.

Time
O(n log k)
Space
O(log k) call stack
function mergeKLists(lists) {
  if (lists.length === 0) 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: O(n log k) time. Avoids the overhead of a heap. The pairwise merge pattern is intuitive and maps directly to merge sort. This is the approach Anduril engineers often prefer — it's predictable and composable.

2. Min-heap (priority queue)

Initialize a min-heap with the head of each non-null list. Repeatedly extract the minimum, append it to the result, and insert the next node from that list.

Time
O(n log k)
Space
O(k)
// JS has no built-in heap; this shows the algorithm structure.
// In a real implementation, use a proper min-heap library.
function mergeKLists(lists) {
  // Simulate with sorted structure insertion for illustration.
  // Real approach: use a min-heap keyed on node.val.
  const dummy = { val: 0, next: null };
  let tail = dummy;
  // Collect all nodes, sort by value — O(n log n) but shows the intent.
  const nodes = [];
  for (const head of lists) {
    let curr = head;
    while (curr) { nodes.push(curr); curr = curr.next; }
  }
  nodes.sort((a, b) => a.val - b.val);
  for (const node of nodes) {
    tail.next = node;
    node.next = null;
    tail = tail.next;
  }
  return dummy.next;
}

Tradeoff: The O(n log n) sort simulation above is for illustration. A true min-heap gives O(n log k). Mention to the interviewer that you'd implement a proper heap in C++ using std::priority_queue or in Python using heapq. In a JS interview, describe the heap approach verbally and implement divide-and-conquer.

Anduril-specific tips

Anduril expects you to know both approaches and compare them. Start by ruling out the O(kn) sequential merge (merge list 1 into list 2, result into list 3, etc.) — this approach processes early elements O(k) times. Then present divide-and-conquer as your primary answer and describe the heap approach as an alternative that's better for k >> n. Mention that in C++, std::priority_queue makes the heap approach concise. The divide-and-conquer is safer in JS where heap isn't built in.

Common mistakes

  • Sequential merge (fold from left) — O(kn) total because the first list's elements are merged k-1 times.
  • Not handling null lists in the divide-and-conquer — when k is odd, the last pair has one null; pass null to mergeTwoLists explicitly.
  • Forgetting to set node.next = null when re-linking in the collect-and-sort approach — creates cycles in the result.
  • Confusing n (total elements) with k (number of lists) in the complexity analysis — O(n log k), not O(k log n).

Follow-up questions

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

  • How would you solve this if the k lists were arriving as real-time streams?
  • What if the lists were doubly linked?
  • Implement a generic merge for k sorted arrays (not linked lists) — can you achieve better cache performance?

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 sequential merge O(kn) not O(n log k)?

Each of the k-1 merges processes all previously merged elements again. If each list has n/k elements, list 1 is merged k-1 times — total O(kn/k * k) = O(kn).

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

There are log k rounds. In each round, every element is touched exactly once across all pairwise merges. Total = n * log k.

Which is faster in practice: heap or divide-and-conquer?

Divide-and-conquer has better cache behavior since it works on contiguous node chains. Heap incurs pointer-chasing overhead for each extraction. For most practical k values, divide-and-conquer is faster.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →