Skip to main content

24. Merge K Sorted Lists

hardAsked at GitHub

Merge k sorted linked lists into one sorted list using a min-heap, analogous to how GitHub merges multiple sorted commit streams from different remotes during a fetch.

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

Problem

Given an array of k linked-list heads, where 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

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. Brute force: collect and sort

Flatten all nodes into an array, sort, then rebuild list — loses linked-list structure advantages.

Time
O(N log N)
Space
O(N)
// Collect all .val into array, sort, rebuild ListNode chain
// Simple but doesn't demonstrate priority-queue skill

Tradeoff:

2. Min-heap (priority queue)

Seed a min-heap with each list's head. Pop the minimum node, append to result, push its next node into heap. Repeat until heap is empty — O(N log k) by keeping heap size at most k.

Time
O(N log k)
Space
O(k)
// JavaScript lacks a built-in heap; simulate with sorted array (ok for interviews)
function mergeKLists(lists) {
  const dummy = new ListNode(0);
  let curr = dummy;
  // Min-heap of [node.val, node]
  const heap = [];
  for (const head of lists) if (head) heap.push(head);
  heap.sort((a,b)=>a.val-b.val);
  while (heap.length) {
    const min = heap.shift();
    curr.next = min;
    curr = curr.next;
    if (min.next) {
      // Insert min.next in sorted position
      let i = 0;
      while (i < heap.length && heap[i].val <= min.next.val) i++;
      heap.splice(i, 0, min.next);
    }
  }
  return dummy.next;
}

Tradeoff:

GitHub-specific tips

GitHub merges sorted commit-timestamp streams during fetch and rebase operations; explain the heap invariant clearly and note that in production you'd use a proper MinHeap class for O(log k) push/pop rather than splice.

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 GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →