Skip to main content

23. Merge k Sorted Lists

hardAsked at Autodesk

Merge k sorted linked lists into one sorted linked list.

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

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge all the lists into one sorted linked list and return it.

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= total nodes <= 10^4

Examples

Example 1

Input
lists=[[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]

Example 2

Input
lists=[]
Output
[]

Approaches

1. Collect, sort, rebuild

Gather all values into an array, sort, then build a single list.

Time
O(N log N)
Space
O(N)
vals=[]; for list of lists walk and push; vals.sort(); build linked list from vals.

Tradeoff:

2. Min-heap of list heads

Push every list's head into a min-heap keyed by value. Pop the smallest, push its next, repeat.

Time
O(N log k)
Space
O(k)
// Reuse a MinHeap keyed by node.val
function mergeKLists(lists) {
  const heap = new MinHeap((a,b) => a.val - b.val);
  for (const head of lists) if (head) heap.push(head);
  const dummy = { next: null };
  let tail = dummy;
  while (heap.size()) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next) heap.push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Autodesk-specific tips

K-way merges show up at Autodesk when streaming sorted geometry chunks out of a BVH build, so heap-based merges land well.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →