23. Merge k Sorted Lists
hardAsked at PinterestPinterest's feed-serving merges sorted streams from N candidate sources every request. Merge k Sorted Lists asks you to merge k sorted linked lists into one sorted list — the min-heap is the canonical answer, with divide-and-conquer as a heap-free alternative.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Pinterest loops.
- Glassdoor (2026-Q1)— Pinterest L4/L5 onsite reports cite Merge k Sorted Lists as the heap / merge round.
- LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list; obvious analog to feed-source merging.
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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending order.The sum of lists[i].length will not exceed 10^4.
Examples
Example 1
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]Example 2
lists = [][]Approaches
1. Concatenate all and sort (brute force)
Walk every list, push all values into a single array, sort, rebuild a linked list.
- Time
- O(N log N) where N = total nodes
- Space
- O(N)
function mergeKListsBrute(lists) {
const vals = [];
for (const head of lists) {
let cur = head;
while (cur) { vals.push(cur.val); cur = cur.next; }
}
vals.sort((a, b) => a - b);
const dummy = { val: 0, next: null };
let cur = dummy;
for (const v of vals) {
cur.next = { val: v, next: null };
cur = cur.next;
}
return dummy.next;
}Tradeoff: Throws away the per-list sorted property — wasted information. Anchor with this then move to the heap.
2. Min-heap of list heads (optimal)
Push the head of each list into a min-heap by value. Pop the smallest, append to result, push that node's next.
- Time
- O(N log k)
- Space
- O(k)
class MinHeap {
constructor() { this.a = []; }
push(v) { this.a.push(v); this._up(this.a.length - 1); }
pop() {
const top = this.a[0];
const last = this.a.pop();
if (this.a.length > 0) { this.a[0] = last; this._down(0); }
return top;
}
size() { return this.a.length; }
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p].val > this.a[i].val) { [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; }
else break;
}
}
_down(i) {
const n = this.a.length;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let best = i;
if (l < n && this.a[l].val < this.a[best].val) best = l;
if (r < n && this.a[r].val < this.a[best].val) best = r;
if (best === i) break;
[this.a[best], this.a[i]] = [this.a[i], this.a[best]];
i = best;
}
}
}
function mergeKLists(lists) {
const heap = new MinHeap();
for (const head of lists) if (head) heap.push(head);
const dummy = { val: 0, next: null };
let cur = dummy;
while (heap.size()) {
const node = heap.pop();
cur.next = node;
cur = cur.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
}Tradeoff: O(N log k) — best general answer. Each node enters and leaves the heap once. Heap size bounded by k. This is the pattern Pinterest's feed-merge service uses.
3. Divide and conquer (no heap)
Pairwise merge adjacent lists, halving the count each round. log k rounds, total O(N log k) work.
- Time
- O(N log k)
- Space
- O(1) extra
function mergeKListsDc(lists) {
if (lists.length === 0) return null;
function merge2(a, b) {
const dummy = { val: 0, next: null };
let cur = dummy;
while (a && b) {
if (a.val <= b.val) { cur.next = a; a = a.next; }
else { cur.next = b; b = b.next; }
cur = cur.next;
}
cur.next = a || b;
return dummy.next;
}
while (lists.length > 1) {
const next = [];
for (let i = 0; i < lists.length; i += 2) {
next.push(merge2(lists[i], lists[i + 1] || null));
}
lists = next;
}
return lists[0];
}Tradeoff: Same asymptotic as the heap version but no extra data structure. Some interviewers prefer this when the language doesn't have a built-in priority queue. Slightly less elegant for streaming follow-ups.
Pinterest-specific tips
Pinterest interviewers grade on whether you can articulate WHY both O(N log k) approaches have the same complexity and pick one for a real reason. 'Heap is better when k is large because rebalancing per insert is O(log k); divide-and-conquer is better when memory matters because no heap allocation' — that's the senior framing. They will pivot to 'now stream the lists' which makes the heap the correct choice.
Common mistakes
- Concatenating all values and sorting — discards the sorted-input information.
- Forgetting to handle empty input lists — pushing null into the heap explodes on .val access.
- Pairwise merging first list with each other in sequence — that's O(N * k), not O(N log k).
- Mutating heap with pop-then-push when peek-then-replace would be more efficient (constant-factor; mention it).
Follow-up questions
An interviewer at Pinterest may pivot to one of these next:
- Stream of k sorted streams — emit merged output as you go.
- Sum of top K elements across all lists.
- Merge by a custom comparator (e.g., timestamp + tiebreaker).
- K-way merge with bounded memory (only top M values fit in RAM).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is heap better than divide-and-conquer asymptotically?
They're identical: both O(N log k). Heap wins on streaming variants because it processes incrementally; D&C requires all lists upfront.
Why does Pinterest specifically care?
Pinterest's feed-merging service combines sorted candidate streams from multiple source services (followed-board pins, recommended pins, trending pins) into a single ranked feed. The k-way merge is the production primitive.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Merge k Sorted Lists and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →