23. Merge K Sorted Lists
hardAsked at LinearMerge k sorted linked lists into one. Linear uses this to see if you know the min-heap approach and can articulate why it's O(n log k) — a natural step up from the easy 'Merge Two Sorted Lists' problem.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Linear loops.
- Glassdoor (2026-Q1)— Cited in Linear SWE onsite reports as a hard data-structures question.
- Blind (2025-12)— Multiple Linear interview threads identify this as a hard follow-up to the merge-two lists warm-up.
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 = [][]Example 3
lists = [[]][]Approaches
1. Brute force: collect all, sort, rebuild
Collect all node values into an array, sort, build a new linked list.
- Time
- O(n log n)
- Space
- O(n)
function mergeKLists(lists) {
const vals = [];
for (const head of lists) {
let curr = head;
while (curr) { vals.push(curr.val); curr = curr.next; }
}
vals.sort((a, b) => a - b);
const dummy = { val: 0, next: null };
let curr = dummy;
for (const v of vals) { curr.next = { val: v, next: null }; curr = curr.next; }
return dummy.next;
}Tradeoff: O(n log n) time, O(n) space. Loses the sorted property of the lists — doesn't use the structure. Mention this only to pivot to the better approaches.
2. Divide and conquer pairwise merge
Recursively merge pairs of lists, halving the problem size each round.
- Time
- O(n log k)
- Space
- O(log k)
function mergeKLists(lists) {
if (!lists.length) return null;
function mergeTwoLists(l1, l2) {
const dummy = { val: -1, next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
while (lists.length > 1) {
const merged = [];
for (let i = 0; i < lists.length; i += 2) {
merged.push(mergeTwoLists(lists[i], lists[i + 1] || null));
}
lists = merged;
}
return lists[0];
}Tradeoff: O(n log k) — each merge round touches n total nodes, and there are log k rounds. O(log k) call stack. Great JavaScript solution without needing a priority queue implementation.
3. Min-heap (canonical optimal)
Initialize a min-heap with the heads of all k lists. Pop the minimum, advance that list's pointer, push the next node. Repeat until heap is empty.
- Time
- O(n log k)
- Space
- O(k)
// JavaScript has no built-in min-heap; pseudocode-style implementation
// In a real interview, implement a MinHeap or use a sorted structure
function mergeKLists(lists) {
// Simulate a min-heap with a sorted array for conceptual clarity
// Production: use a proper MinHeap with O(log k) push/pop
const heap = [];
for (const head of lists) if (head) heap.push(head);
heap.sort((a, b) => a.val - b.val);
const dummy = { val: -1, next: null };
let curr = dummy;
while (heap.length) {
const node = heap.shift(); // O(k) — replace with O(log k) heap pop in production
curr.next = node;
curr = curr.next;
if (node.next) {
// Insert node.next into sorted position — O(log k) with a real heap
heap.push(node.next);
heap.sort((a, b) => a.val - b.val);
}
}
return dummy.next;
}Tradeoff: True O(n log k) with a proper min-heap. In JavaScript, note that there's no built-in — show the conceptual approach, explain the heap operations, and offer to implement a MinHeap if the interviewer asks. Many Linear interviewers accept the divide-and-conquer approach as equivalent.
Linear-specific tips
Walk through the progression: brute force O(n log n) → divide and conquer O(n log k) → min-heap O(n log k). Linear interviewers want to see the k-factor reasoning: 'At each step, I'm choosing the minimum of k candidates — a heap does that in O(log k) instead of O(k) per step.' In JavaScript specifically, the divide-and-conquer approach is often more practical since it avoids implementing a heap from scratch.
Common mistakes
- Implementing sequential merging instead of pairwise — merging lists one at a time is O(n*k), much worse than O(n log k).
- Forgetting to handle null lists in the input — check lists[i+1] || null in the pairwise merge loop.
- Claiming a sort-based approach is O(n log k) — sorting n elements is O(n log n), not O(n log k).
Follow-up questions
An interviewer at Linear may pivot to one of these next:
- Merge Two Sorted Lists (LC 21) — the building block for this problem.
- Find K Pairs with Smallest Sums (LC 373) — similar heap-based selection pattern.
- How does your solution change if you need to merge k sorted arrays instead of linked lists?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why O(n log k) and not O(n log n)?
The heap always contains at most k elements. Each push/pop operation is O(log k). With n total nodes processed, the total is O(n log k). When k << n, this is significantly better than O(n log n).
Why is sequential merging O(n*k)?
Merging list 1 with list 2 costs O(n). Then merging the result with list 3 costs O(2n). The total is O(n + 2n + ... + kn) = O(n*k^2/2) ≈ O(n*k).
How do I implement a min-heap in JavaScript?
Use an array with index-based parent/child relationships: parent at i, children at 2i+1 and 2i+2. Implement siftDown and siftUp. For interviews, offer to pseudocode it or use the divide-and-conquer equivalent.
Practice these live with InterviewChamp.AI
Drill Merge K Sorted Lists and other Linear interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →