23. Merge K Sorted Lists
hardAsked at ShopifyMerge K Sorted Lists is Shopify's heap-vs-divide-and-conquer hard. Real motivation: merging time-ordered event streams from K shards into one chronological feed. The interviewer is grading whether you discuss BOTH approaches.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Senior Backend onsites cite Merge K Sorted Lists as the standard hard linked-list round.
- Blind (2025-12)— Shopify L4+ interview reports include Merge K Sorted Lists with the heap follow-up.
Problem
You are given an array of k linked-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. Brute-force collect + sort
Walk all lists, push every value to one array, sort, rebuild a list.
- Time
- O(N log N) where N is 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 tail = dummy;
for (const v of vals) {
tail.next = { val: v, next: null };
tail = tail.next;
}
return dummy.next;
}Tradeoff: Simplest correct version. Drops to O(N log N), same as the heap version asymptotically — but doesn't preserve the linked-list structure assumption. Use only as warm-up.
2. Min-heap of k head pointers (optimal)
Push all list heads into a min-heap by value. Pop the smallest, append it to the result, push its .next.
- Time
- O(N log k)
- Space
- O(k)
class MinHeap {
constructor() { this.h = []; }
size() { return this.h.length; }
push(node) { this.h.push(node); this._up(this.h.length - 1); }
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length) { this.h[0] = last; this._down(0); }
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p].val > this.h[i].val) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
else break;
}
}
_down(i) {
const n = this.h.length;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < n && this.h[l].val < this.h[smallest].val) smallest = l;
if (r < n && this.h[r].val < this.h[smallest].val) smallest = r;
if (smallest === i) break;
[this.h[smallest], this.h[i]] = [this.h[i], this.h[smallest]];
i = smallest;
}
}
}
function mergeKLists(lists) {
const heap = new MinHeap();
for (const head of lists) if (head) heap.push(head);
const dummy = { val: 0, next: null };
let tail = dummy;
while (heap.size()) {
const node = heap.pop();
tail.next = node;
tail = node;
if (node.next) heap.push(node.next);
}
tail.next = null;
return dummy.next;
}Tradeoff: O(N log k) time, O(k) extra space. The standard 'tournament' answer. Each node enters and exits the heap once; heap ops are O(log k).
3. Divide-and-conquer pairwise merge
Pairwise merge lists into k/2, k/4, ..., 1 sub-list. Each level is O(N) work over log k levels.
- Time
- O(N log k)
- Space
- O(1) extra (in-place pointer rewiring)
function mergeTwoLists(a, b) {
const dummy = { val: 0, next: null };
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a || b;
return dummy.next;
}
function mergeKListsDC(lists) {
if (!lists.length) return null;
while (lists.length > 1) {
const next = [];
for (let i = 0; i < lists.length; i += 2) {
next.push(mergeTwoLists(lists[i], lists[i + 1] || null));
}
lists = next;
}
return lists[0];
}Tradeoff: Same O(N log k) but with NO heap overhead and constant extra space. In practice, often faster than the heap version on small k. Shopify senior interviewers love when candidates volunteer this as the cleaner alternative.
Shopify-specific tips
Shopify's expected dialogue: name BOTH the heap and the divide-and-conquer approach. Justify your choice. If you wrote the heap version first, expect 'can you do it without a heap?' — pivot to divide-and-conquer. Senior candidates write the divide-and-conquer FIRST because it's simpler.
Common mistakes
- Forgetting to filter out null lists when initializing the heap.
- Forgetting tail.next = null at the end — the last node might have an unintended .next pointer.
- Re-allocating new ListNode objects instead of rewiring existing ones — works but wastes memory.
- In divide-and-conquer, merging lists[0] with lists[2] with lists[4] sequentially — that's the slow O(kN), not the pairwise O(N log k).
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- What if lists were infinite streams? (Heap with cursor per stream.)
- Merge K Sorted Arrays (not linked lists).
- Smallest Range Covering Elements from K Lists (LeetCode 632).
- External sort — what if K * N doesn't fit in memory?
- What if values are not comparable directly but via a key function?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Heap vs divide-and-conquer — which one to write?
Both are O(N log k). Divide-and-conquer is shorter and faster in practice for small k. Heap generalizes to streaming inputs. Shopify accepts either; volunteer the OTHER one as the follow-up answer.
Why not just concatenate and sort?
Same asymptotic O(N log N) but you lose the structure (the inputs are already sorted). For unsorted inputs, sorting is the right answer. For sorted inputs, heap or D&C wins because O(N log k) < O(N log N) when k < N.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Merge K Sorted Lists and other Shopify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →