Skip to main content

23. Merge K Sorted Lists

hardAsked at Hugging Face

Merge k sorted linked lists into one sorted list efficiently. Hugging Face uses this to assess whether candidates can compose primitives (min-heap, divide-and-conquer) for distributed inference — the same pattern used when merging ranked result streams from multiple model shards serving parallel requests.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Cited in Hugging Face SWE onsite reports as a hard problem testing heap-based multi-stream merging.
  • Blind (2025-11)— Hugging Face interview threads list Merge K Sorted Lists as a flagship hard problem for infrastructure and ML platform 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: Empty input — return null.

Example 3

Input
lists = [[]]
Output
[]

Explanation: Single empty list.

Approaches

1. Min-heap (priority queue)

Initialize a min-heap with the head of each non-null list. Extract the minimum, advance that list's pointer, push the next node. Repeat until the heap is empty.

Time
O(n log k) where n is total nodes
Space
O(k) for the heap
// JS doesn't have a built-in heap; showing the algorithm with a sorted array simulation
// In a real implementation use a MinHeap class or Python's heapq
function mergeKLists(lists) {
  // Collect all nodes, sort, rebuild list (O(n log n) — illustrates the idea)
  // For true O(n log k), implement a min-heap:
  const dummy = { val: 0, next: null };
  let tail = dummy;
  // Simulated min-heap via sorted insertion for interview illustration
  const heap = [];
  for (const head of lists) {
    if (head !== null) heap.push(head);
  }
  // Binary-search insert helper (O(log k) per operation)
  function heapPush(node) {
    let lo = 0, hi = heap.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (heap[mid].val <= node.val) lo = mid + 1;
      else hi = mid;
    }
    heap.splice(lo, 0, node);
  }
  // Re-initialize with binary search inserts
  const initial = heap.splice(0);
  for (const node of initial) heapPush(node);
  while (heap.length) {
    const node = heap.shift(); // extract min (O(1) from front of sorted array)
    tail.next = node;
    tail = tail.next;
    if (node.next !== null) heapPush(node.next);
  }
  return dummy.next;
}

Tradeoff: True O(n log k) with a proper binary heap. In JS, explain the algorithm using a MinHeap class and implement it. The key insight: at any time we only need to know the current minimum across k lists — a heap of size k is sufficient.

2. Divide and conquer (pair-wise merge)

Recursively merge pairs of lists. Each merge round reduces k lists to k/2 lists. After log(k) rounds, one list remains.

Time
O(n log k)
Space
O(log k) recursion depth
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) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i+1] : null;
      merged.push(mergeTwoLists(l1, l2));
    }
    lists = merged;
  }
  return lists[0];
}

Tradeoff: O(n log k) time and O(1) extra space (besides O(log k) call stack in recursive form). Elegant and doesn't require a heap implementation. Each node is merged O(log k) times total. This is often the cleaner solution in a JS interview context.

Hugging Face-specific tips

Hugging Face will ask: 'Why is this O(n log k) and not O(nk)?' For the heap approach: 'Each extraction from a k-element heap is O(log k), and we do n total extractions.' For divide-and-conquer: 'Each node participates in O(log k) merge rounds, and each round's total work across all pairs is O(n).' Connect to their infrastructure: 'This is exactly how we merge ranked completion streams from multiple inference replicas in a load-balanced serving cluster — each shard returns a sorted partial result and a heap-merge gives the final ranking.'

Common mistakes

  • Naive sequential merge — merging each list one by one is O(nk), not O(n log k).
  • Pushing null nodes into the heap — always check node !== null before heapPush.
  • In divide-and-conquer, off-by-one when k is odd — handle the unpaired last list explicitly.
  • Forgetting the empty-input edge case — return null when lists is empty or all lists are empty.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • How would you merge K sorted streams arriving in real time without buffering all inputs?
  • Merge K Sorted Arrays — same algorithm but with arrays (simpler indexing, same complexity).
  • How does this scale if K = 10^6 and each list has 10^6 nodes? (Disk-based external merge sort)

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 only ever holds k elements (one per list). Each heap operation is O(log k), not O(log n). Since n can be >> k, this is a meaningful improvement.

Which approach is better — heap or divide-and-conquer?

Asymptotically equivalent. The heap approach generalizes naturally to online/streaming scenarios. Divide-and-conquer is simpler to implement in JS (no heap needed) and reuses the two-list merge primitive.

What if the k lists are not linked lists but arrays?

Same algorithm — use index pointers instead of node pointers. The heap stores (value, listIndex, elementIndex) tuples.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →