Skip to main content

22. Merge K Sorted Lists

hardAsked at Glassdoor

Glassdoor's feed merges sorted review streams from multiple data sources in real time — this k-way merge problem is their hard-tier benchmark for candidates who know when to reach for a min-heap instead of naive repeated comparisons.

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

Problem

Given an array of k linked lists, each sorted in ascending order, merge all 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
  • Total nodes across all lists <= 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. Sequential merge (divide and conquer)

Repeatedly merge pairs of lists bottom-up until one remains. Each merge level costs O(n); with log k levels total cost is O(n log k).

Time
O(n log k)
Space
O(log k)
class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
    else { cur.next = l2; l2 = l2.next; }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}

function mergeKLists(lists) {
  if (!lists.length) return null;
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

Tradeoff:

2. Min-heap simulation with array

Collect all node values, sort them, then rebuild the list. O(n log n) but simpler to implement in JS without a native heap library. In production, a proper min-heap gives O(n log k).

Time
O(n log n)
Space
O(n)
function mergeKLists(lists) {
  const vals = [];
  for (let head of lists) {
    while (head) {
      vals.push(head.val);
      head = head.next;
    }
  }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let cur = dummy;
  for (const v of vals) {
    cur.next = { val: v, next: null };
    cur = cur.next;
  }
  return dummy.next;
}

Tradeoff:

Glassdoor-specific tips

Glassdoor interviewers expect you to name the O(n log k) min-heap approach even if you implement the array-sort version in JS. Explain: 'in a production system I'd use a min-heap initialized with the heads of all k lists — each extraction is O(log k) and we do n total, giving O(n log k).' They grade clarity of tradeoff reasoning as much as working code. Divide-and-conquer merge is also accepted and runs in O(n log k) without a heap.

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

Practice these live with InterviewChamp.AI →