Skip to main content

23. Merge K Sorted Lists

hardAsked at Broadcom

Merge k sorted linked lists into one sorted list efficiently. Broadcom asks this because multi-queue merging is a real operation in packet schedulers and priority-queue-based traffic shaping in Broadcom's Tomahawk switching ASICs — merging k traffic classes in O(n log k) is a production requirement.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Cited in Broadcom SWE senior onsite reports as a hard problem testing heap-based multi-source merging.
  • Blind (2025-11)— Broadcom infrastructure and networking software threads list Merge K Sorted Lists as a high-signal hard problem.

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 order.

Example 2

Input
lists = []
Output
[]

Explanation: No lists to merge.

Example 3

Input
lists = [[]]
Output
[]

Explanation: One empty list — result is empty.

Approaches

1. Divide and conquer (pair-wise merge)

Repeatedly merge pairs of lists. In each round, the number of lists halves. After log(k) rounds, all lists are merged. Each round processes O(n) total nodes.

Time
O(n log k)
Space
O(1) extra per merge, O(log k) recursion
function mergeTwo(l1, l2) {
  const dummy = { next: null };
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}
function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwo(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

Tradeoff: O(n log k) time, O(1) extra space per merge. No auxiliary data structure needed. Elegant and cache-friendly. Well-suited for embedded contexts where heap allocation is expensive.

2. Min-heap (simulated with sorted array in JS)

Push the head of each list into a min-heap. Repeatedly extract the minimum node, append to result, and push that node's next into the heap. Repeat until heap is empty.

Time
O(n log k)
Space
O(k)
// JS has no built-in heap; simulate with a sorted buffer for small k
// In a real system, use a proper MinHeap class
function mergeKLists(lists) {
  // Min-heap simulation using sorted array (acceptable for interview illustration)
  const heap = [];
  const push = (node) => {
    heap.push(node);
    heap.sort((a, b) => a.val - b.val);
  };
  const pop = () => heap.shift();
  for (const head of lists) if (head) push(head);
  const dummy = { next: null };
  let curr = dummy;
  while (heap.length > 0) {
    const node = pop();
    curr.next = node;
    curr = curr.next;
    if (node.next) push(node.next);
  }
  return dummy.next;
}

Tradeoff: Conceptually O(n log k) with a real heap; this simulation uses sort which is O(k log k) per operation. In the interview, describe the min-heap approach theoretically and note that JavaScript lacks a built-in heap — implement MinHeap or describe the divide-and-conquer alternative.

Broadcom-specific tips

At Broadcom, lead with the divide-and-conquer approach: 'I merge lists pair-wise, halving the number of lists each round — O(log k) rounds × O(n) work per round = O(n log k) total.' Then describe the min-heap conceptually: 'A heap of k heads also gives O(n log k) but requires O(k) extra space — useful when you need to interleave elements from all streams simultaneously, as in a multi-priority packet scheduler.' Broadcom interviewers appreciate the space vs streaming-access trade-off discussion.

Common mistakes

  • Naive concatenate-and-sort: O(n log n) total — suboptimal and misses the point.
  • Sequential two-list merges without divide-and-conquer: O(nk) — degrades badly for large k.
  • Not handling empty lists or null heads in the heap — heap operations on null nodes cause runtime errors.
  • In divide-and-conquer, wrong pairing indices — ensure you pair i with i+interval and update interval correctly.

Follow-up questions

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

  • How would you merge k sorted arrays instead of linked lists?
  • How does this change if lists arrive as a stream (you don't know k upfront)?
  • What is the external sort algorithm and how does it use this same merge step?

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 the naive sequential merge O(nk)?

Each merge of two lists of size m and n costs O(m+n). If you merge sequentially, the running list grows: O(n) + O(2n) + ... + O(kn) = O(nk²/2) — quadratic in k.

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

Each of the log k rounds processes all n nodes once. Total work = O(n) × log k rounds = O(n log k).

When would a min-heap be preferable over divide-and-conquer?

When you need to interleave nodes from all k sources simultaneously — e.g., streaming merge where you want the globally smallest element at each step, not just a final sorted list.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →