Skip to main content

23. Merge K Sorted Lists

hardAsked at HubSpot

HubSpot asks Merge K Sorted Lists to see whether you can reason about multi-source merging with a priority queue — a design pattern central to their event-stream aggregation where k data sources need to be merged in order for the activity feed.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE onsite reports mention Merge K Sorted Lists as a hard problem testing heap-based multi-source merging.
  • Blind (2025-10)— Listed in HubSpot interview threads as a high-signal hard problem for senior SWE 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: pick the minimum head at each step.

Approaches

1. Divide and conquer (pair-wise merge)

Repeatedly pair up lists and merge each pair using the O(m+n) two-list merge. After each round the number of lists halves. After log(k) rounds, one merged list remains.

Time
O(N log k) where N is total nodes
Space
O(log k) recursion
function mergeKLists(lists) {
  if (lists.length === 0) return null;
  function mergeTwoLists(l1, l2) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    while (l1 && l2) {
      if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
      else { curr.next = l2; l2 = l2.next; }
      curr = curr.next;
    }
    curr.next = l1 || l2;
    return dummy.next;
  }
  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];
}

Tradeoff: O(N log k) time, O(1) extra space (beyond recursion). No external heap needed. The pair-wise structure mirrors merge sort. A clean answer when a min-heap is unavailable in JavaScript.

2. Min-heap (priority queue)

Initialize a min-heap with the head of each list. Pop the minimum, append to result, push its next node back into the heap. Repeat until the heap is empty.

Time
O(N log k)
Space
O(k) heap
// JavaScript has no built-in min-heap; implement or use divide-and-conquer.
// Conceptual pseudocode:
function mergeKLists(lists) {
  // MinHeap is a custom min-heap class by node value
  const heap = new MinHeap((a, b) => a.val - b.val);
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null };
  let curr = dummy;
  while (!heap.isEmpty()) {
    const node = heap.pop();
    curr.next = node;
    curr = curr.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) time, O(k) heap space. Elegant and generalizes naturally to streaming merges. In JavaScript, you must implement a min-heap from scratch — state this and use divide-and-conquer as the practical alternative. In Java/Python, PriorityQueue/heapq make this approach direct.

HubSpot-specific tips

State both approaches: 'I can use a min-heap for O(N log k) or divide-and-conquer pair merges — both have identical complexity. In JavaScript I'd use divide-and-conquer since there's no built-in heap; in Java/Python I'd use a PriorityQueue.' HubSpot values language awareness. They often ask to justify O(N log k) vs. naive O(Nk) sequential merges — explain that log k rounds of pair merges each scan N total nodes.

Common mistakes

  • Naive sequential merge (merge list 1+2, then result+3, ...) — O(Nk) instead of O(N log k).
  • In the heap approach, forgetting to push node.next after popping node — the remaining list gets orphaned.
  • Not handling empty lists in the input array — skip null list heads when initializing the heap.
  • Returning lists[0] without verifying the lists array is non-empty — return null for empty input.

Follow-up questions

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

  • Merge K Sorted Arrays — same pattern but with index tracking instead of linked-list pointers.
  • Find the Median from a Data Stream (LC 295) — uses two heaps to maintain the median.
  • How would you merge k streams in real time without loading all nodes into memory?

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 divide-and-conquer O(N log k) and not O(N * k)?

In divide-and-conquer, each of the N nodes is merged log k times (one per halving round). In naive sequential merges, later merges process longer and longer lists, costing O(Nk) total.

Why use a dummy head node?

It simplifies the code by letting you always do curr.next = node without special-casing an empty result list. Return dummy.next at the end.

Does divide-and-conquer change the relative order of equal elements?

No — mergeTwoLists uses <=, which is stable. Equal elements from earlier lists precede equal elements from later lists, matching the input order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →