Skip to main content

92. Merge k Sorted Lists

hardAsked at Datadog

Merge k sorted linked lists into one sorted list. Datadog asks this because their query layer routinely merges K ordered metric shards into a unified stream — the min-heap pattern is identical.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — query-layer shard merge.
  • Blind (2025-12)— Recurring at Datadog.

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]

Example 2

Input
lists = []
Output
[]

Approaches

1. Concat and sort

Collect all values; sort; rebuild.

Time
O(N log N)
Space
O(N)
// Push every val into array; sort; rebuild list.

Tradeoff: Ignores per-list sortedness. Datadog will fail this for not exploiting input structure.

2. Min-heap of head pointers (optimal)

Initialize heap with all heads. Pop min, append to result, push its next.

Time
O(N log k)
Space
O(k)
// Use a MinHeap keyed on 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 = { val: 0, next: null };
  let tail = dummy;
  while (heap.size > 0) {
    const n = heap.pop();
    tail.next = n;
    tail = n;
    if (n.next) heap.push(n.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) — best for large k. Datadog-canonical: this IS the algorithm for K-way merge over sorted streams.

Datadog-specific tips

Datadog will probe: 'Divide-and-conquer merge alternative?' Pair-merge lists log k times — same O(N log k). Equivalent complexity but no heap needed. Articulate when each wins (heap better for streaming; D&C better when all lists fit in memory).

Common mistakes

  • Pushing nodes into heap without considering null — null heads must be filtered.
  • Forgetting dummy head — special-cases the result head.
  • Using max-heap by mistake — wrong direction.

Follow-up questions

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

  • Merge Two Sorted Lists (LC 21) — base case.
  • Smallest Range Covering K Lists (LC 632) — same heap pattern.
  • Datadog-style: K-way merge of sorted metric shards.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or divide-and-conquer?

Both are O(N log k). Heap is streaming-friendly; D&C uses no extra structure beyond merge-two-list buffer.

Why not heap of all N values?

That's O(N log N). The heap-of-heads trick exploits per-list sortedness.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →