Skip to main content

83. Merge k Sorted Lists

hardAsked at Plaid

Merge k sorted linked lists into one sorted list. Plaid asks this because merging k pre-sorted bank-feed streams into a unified ledger is exactly this primitive — it's their core ETL fan-in operation.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — multi-feed merge classic.
  • Blind (2026)— Plaid backend platform OA.

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. Repeatedly pick min by scanning all heads

Pick min head each step.

Time
O(N * k) where N = total nodes
Space
O(1)
// k * N. Too slow when k is large.

Tradeoff: TLE for k=10^4.

2. Min-heap of list heads

Push every list's head into a min-heap. Pop the min, push its next.

Time
O(N log k)
Space
O(k)
// Heap-based — needs a PriorityQueue. Pseudo:
// pq = new MinHeap(compareByVal)
// for (l of lists) if (l) pq.push(l)
// while (pq.size) { node = pq.pop(); tail.next = node; if (node.next) pq.push(node.next); ... }

Tradeoff: Heap maintains k candidates; each pop is O(log k). Total N log k.

Plaid-specific tips

Plaid uses this exact algorithm for their ETL fan-in. Bonus signal: discuss the divide-and-conquer alternative — merge lists pairwise in log k rounds. Same asymptotic, but each merge is a simple two-list merge instead of heap-based, which is easier to debug in production.

Common mistakes

  • Pushing all nodes into the heap upfront — O(N) space instead of O(k).
  • Not handling empty lists.
  • Comparator returning a non-numeric — JS heap libs vary, be explicit.

Follow-up questions

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

  • Merge two sorted lists (LC 21).
  • K-way merge of arrays.
  • External sort — when lists don't fit in 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

Heap vs divide-and-conquer?

Same asymptotic (N log k). Heap uses k extra space; D&C uses log k recursion. In Plaid's ETL the divide-and-conquer is preferred because each pairwise merge is simpler and easier to instrument.

What if k = 0 or all lists are empty?

Heap starts empty, return null. The pre-pop empty-check handles this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →