Skip to main content

83. Merge k Sorted Lists

hardAsked at Salesforce

Merge k sorted linked lists into one sorted list. Salesforce uses this directly in their Bulk API result aggregation across multiple partitions.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce Bulk API result aggregation uses k-way merge.
  • Blind (2025-12)— Recurring on Salesforce L5+ onsites.

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
[]

Example 3

Input
lists = [[]]
Output
[]

Approaches

1. Brute force concatenate and sort

Collect all values, sort, build a list.

Time
O(N log N)
Space
O(N)
// Loses the sorted invariant.

Tradeoff: Wastes the partial-sortedness. Salesforce will push for k-way merge.

2. Pairwise merge (divide and conquer)

Repeatedly merge adjacent pairs. Halves the count of lists each round.

Time
O(N log k)
Space
O(log k) recursion
function mergeKLists(lists) {
  if (!lists.length) return null;
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      merged.push(mergeTwo(lists[i], lists[i + 1] || null));
    }
    lists = merged;
  }
  return lists[0];
}
function mergeTwo(a, b) {
  const d = { next: null };
  let c = d;
  while (a && b) {
    if (a.val <= b.val) { c.next = a; a = a.next; } else { c.next = b; b = b.next; }
    c = c.next;
  }
  c.next = a || b;
  return d.next;
}

Tradeoff: O(N log k). Avoids the per-element heap overhead. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses k-way merge directly in their Bulk API result aggregation across multiple partitions. They specifically grade on whether you reach for divide-and-conquer (O(N log k)) rather than naive sequential merge (O(N*k)). Bonus signal: discuss the min-heap alternative — same O(N log k) but easier to reason about when streaming.

Common mistakes

  • Sequential merge — start with list 0, merge with 1, then 2 — gives O(N*k) which TLEs.
  • Heap-based without a real heap library — using sort() as a proxy makes it O(N k log k).
  • Not handling odd lists.length — must merge with null on the last pair.

Follow-up questions

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

  • Merge k sorted arrays (not lists).
  • Merge intervals (LC 56).
  • Streaming k-way merge with lazy initialization.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Pairwise merge vs min-heap?

Both are O(N log k). Pairwise is more cache-friendly and easier to parallelize. Heap is more flexible (online/streaming additions).

Why is it O(N log k), not O(N log N)?

Each element participates in log k merges (halving each round). Total work is O(N log k), which beats sort-then-emit's O(N log N).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →