Skip to main content

23. Merge K Sorted Lists

hardAsked at AMD

Merge k sorted linked lists into one sorted list. AMD uses this to test min-heap design and divide-and-conquer — both strategies appear in GPU command queue aggregation, multi-stream kernel scheduling, and external merge sort over large datasets that exceed on-chip memory.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE hard-round candidates report Merge K Sorted Lists with both heap and D&C approaches expected.
  • Blind (2025-10)— AMD interview threads mark this as a hard problem testing heap design and external sort awareness relevant to GPU driver work.

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: Three sorted lists merged into one.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input.

Approaches

1. Min-Heap

Push the head of each non-null list into a min-heap. Repeatedly extract the minimum node, attach it to the result, and push that node's next (if any) back into the heap.

Time
O(N log k) where N = total nodes
Space
O(k) for the heap
// JS lacks a built-in heap; simulate with a sorted structure for clarity.
// In a real interview, describe the heap and implement extract-min manually.
function mergeKLists(lists) {
  const dummy = { next: null };
  let tail = dummy;
  // Priority queue simulation: store [val, node] pairs sorted by val
  const heap = [];
  const push = (node) => {
    if (!node) return;
    heap.push(node);
    heap.sort((a, b) => a.val - b.val); // O(k log k) per op; real heap is O(log k)
  };
  for (const head of lists) push(head);
  while (heap.length) {
    const node = heap.shift();
    tail.next = node;
    tail = tail.next;
    push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) with a real heap; the simulated sort here is O(N k log k). In Java/C++ use a PriorityQueue — mention this to the interviewer and describe the O(log k) heap operations explicitly.

2. Divide and Conquer (pairwise merge)

Pair up lists and merge each pair. Repeat until one list remains. O(log k) rounds, each round merges O(N) total nodes.

Time
O(N log k)
Space
O(log k) call stack
function mergeKLists(lists) {
  if (!lists.length) return null;
  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];
}
function mergeTwoLists(l1, l2) {
  const dummy = { 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 — same as heap, but fully O(1) auxiliary space per level (only the call/iteration stack). This approach is more cache-friendly as it works on contiguous pairs rather than maintaining a heap across arbitrary nodes.

AMD-specific tips

AMD external-sort use cases (sorting GPU telemetry streams, merging multi-channel profiler data) make this problem directly relevant. Name the two approaches and their trade-offs upfront: 'The heap approach is O(N log k) with O(k) space; divide-and-conquer is also O(N log k) but with better cache behavior and no heap overhead.' AMD engineers care about memory access patterns — the pairwise D&C approach touches data in more cache-friendly order. Mention that for k=2 both reduce to the simpler merge two lists problem.

Common mistakes

  • Using O(N log N) sort on all values collected into an array — correct but misses the structured O(N log k) optimization.
  • Not handling empty lists in the input array — push only non-null heads into the heap.
  • In D&C: naively re-creating the pair array every round instead of advancing indices — leads to extra allocation.
  • Forgetting the dummy head node in mergeTwoLists — causes special-casing for the first element.

Follow-up questions

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

  • Find K-th Smallest Element in k Sorted Arrays — heap approach generalizes directly.
  • How would you merge k GPU profiler trace files (each sorted by timestamp) on disk?
  • What is the time complexity if k = N (each list has exactly one element)?

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

The heap always contains at most k elements (one per list). Each of the N total insert/extract operations costs O(log k), giving O(N log k) total — much better than O(N log N) for small k.

When is D&C better than the heap?

D&C avoids heap memory overhead and has better cache access patterns for in-memory lists. The heap shines when you need to interleave results immediately (streaming output) rather than waiting for a full merge.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →