Skip to main content

23. Merge K Sorted Lists

hardAsked at eBay

eBay's search ranking system merges sorted result streams from k independent indices — seller inventory, product catalog, auction listings — into a single ordered result set. Merge K Sorted Lists is the algorithmic core. It elevates the two-list merge (LC 21) to a k-way problem requiring a min-heap, which eBay uses to separate candidates who truly understand priority queue mechanics.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Reported as a high-frequency eBay hard problem in senior SWE and staff onsite rounds.
  • Blind (2025-12)— eBay SWE threads cite Merge K Sorted Lists as a key hard problem that distinguishes senior from mid-level candidates.

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: Merge three sorted lists: repeatedly extract the minimum head across all active lists.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input returns null.

Example 3

Input
lists = [[]]
Output
[]

Explanation: Single empty list returns null.

Approaches

1. Min-Heap (Priority Queue)

Initialize a min-heap with the heads of all non-null lists. Repeatedly extract the minimum node, append it to the result, and push its successor onto the heap.

Time
O(N log k) where N is total nodes and k is number of lists
Space
O(k) for the heap
// JavaScript has no built-in min-heap; simulate with a sorted structure
// In an interview, declare: 'I'll use a min-heap / priority queue here.'
// This implementation uses a simple sorted array for clarity:
function mergeKLists(lists) {
  // Min-heap simulated with insertion sort (acceptable for interviews;
  // in production use a proper heap library)
  const heap = [];
  const push = (node) => {
    heap.push(node);
    heap.sort((a, b) => a.val - b.val); // O(k log k) per push in this simulation
  };
  for (const head of lists) if (head) push(head);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.length > 0) {
    const node = heap.shift();
    tail.next = node;
    tail = tail.next;
    if (node.next) push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) with a true min-heap. The array-sort simulation above is O(N * k log k) — acceptable for demonstrating the concept in JS interviews where a heap library is unavailable. State: 'In Java I'd use PriorityQueue; in production JS I'd use a heap library or implement one.'

2. Divide and Conquer (pair-wise merge)

Pair up lists and merge each pair. Repeat until one list remains. This is merge sort applied to the list of lists.

Time
O(N log k)
Space
O(log k) call stack
function mergeKLists(lists) {
  if (lists.length === 0) return null;
  function mergeTwoLists(l1, l2) {
    const dummy = { val: 0, 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;
  }
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      merged.push(mergeTwoLists(lists[i], lists[i + 1] || null));
    }
    lists = merged;
  }
  return lists[0];
}

Tradeoff: O(N log k) — same complexity as heap, but uses the merge-two-lists primitive iteratively. Avoids needing a heap implementation and is often easier to code correctly under interview time pressure. eBay interviewers accept this as the preferred JavaScript answer.

eBay-specific tips

eBay interviewers frame this as a real-world merging challenge: 'We have k sorted result streams; design an efficient merge.' Lead with the heap approach to show you know the optimal data structure, then offer divide-and-conquer as the JavaScript-friendly implementation. Key complexity to state: 'N log k — N total nodes, each touched once; heap operations are O(log k).' For the scale follow-up: 'At eBay's search volume with millions of results, this would be distributed — split k into partitions, merge locally, then merge partition results.'

Common mistakes

  • Naively merging lists one by one — O(kN) total, where each merge of a growing list against a new list is increasingly expensive.
  • Pushing all node values into an array, sorting, and rebuilding — O(N log N) and loses the k-way merge structure the interviewer wants to see.
  • Not handling null lists or empty lists in the heap initialization — causes null pointer exceptions.
  • In the divide-and-conquer approach, not handling odd-length list arrays — the unpaired last list must be carried forward as-is.

Follow-up questions

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

  • Merge Two Sorted Lists (LC 21) — the base case this problem builds on.
  • Find K Pairs with Smallest Sums (LC 373) — similar heap-based k-way selection.
  • How would you implement a true min-heap in JavaScript from scratch?

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 contains at most k elements at any time (one head per list). Each push/pop is O(log k). Over N total nodes, the total cost is O(N log k). log k < log N when k < N, which is typical.

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

There are log k rounds of merging. In each round, every node is touched exactly once (across all pairs). Total: N nodes * log k rounds = O(N log k).

What is the best approach in a Java interview?

PriorityQueue<ListNode> with a comparator on node values. Java's built-in min-heap makes the heap approach clean and concise — the interviewer-expected canonical answer at eBay where Java is the primary language.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →