23. Merge K Sorted Lists
hardAsked at HPHP's enterprise print-management servers merge sorted job queues from thousands of network printers into a single priority-ordered dispatch stream. Merge K Sorted Lists tests exactly this pattern — combining multiple sorted streams efficiently using a min-heap or divide-and-conquer, skills that matter in HP's large-scale IT infrastructure.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in HP loops.
- Glassdoor (2025-Q4)— HP SWE senior onsite reports cite Merge K Sorted Lists as a hard question used in later rounds for systems engineers.
- Blind (2025-09)— HP interview prep threads include Merge K Sorted Lists as a representative hard problem for infrastructure and data-pipeline roles.
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].val <= 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]Explanation: Merging three sorted lists into one sorted result.
Example 2
lists = [][]Explanation: No lists to merge.
Example 3
lists = [[]][]Explanation: One empty list.
Approaches
1. Min-heap (priority queue)
Insert the head of each list into a min-heap. Repeatedly extract the minimum node, attach it to the result, and push its next node into the heap.
- Time
- O(N log k) where N is total nodes, k is number of lists
- Space
- O(k)
// JavaScript doesn't have a built-in min-heap; implement a simple one.
class MinHeap {
constructor() { this.heap = []; }
push(node) {
this.heap.push(node);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) { this.heap[0] = last; this._siftDown(0); }
return top;
}
_bubbleUp(i) {
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.heap[p].val <= this.heap[i].val) break;
[this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
i = p;
}
}
_siftDown(i) {
const n = this.heap.length;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.heap[l].val < this.heap[smallest].val) smallest = l;
if (r < n && this.heap[r].val < this.heap[smallest].val) smallest = r;
if (smallest === i) break;
[this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
i = smallest;
}
}
get size() { return this.heap.length; }
}
function mergeKLists(lists) {
const heap = new MinHeap();
for (const head of lists) if (head) heap.push(head);
const dummy = { val: 0, next: null };
let curr = dummy;
while (heap.size > 0) {
const node = heap.pop();
curr.next = node;
curr = curr.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
}Tradeoff: O(N log k) — optimal for k lists with N total nodes. Heap size is at most k at any point. Requires implementing a min-heap in JS (or noting you'd use a library in production).
2. Divide and conquer (pair-wise merge)
Merge pairs of lists, halving the problem each round. After log k rounds, all lists are merged into one.
- Time
- O(N log k)
- Space
- O(log k) recursion stack
function mergeTwoLists(l1, l2) {
const dummy = { val: 0, 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;
}
function mergeKLists(lists) {
if (lists.length === 0) return null;
let interval = 1;
while (interval < lists.length) {
for (let i = 0; i + interval < lists.length; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}Tradeoff: Same O(N log k) complexity, avoids heap implementation. The iterative version uses O(1) extra space beyond the output.
HP-specific tips
HP interviewers often ask which approach you'd choose in production — the divide-and-conquer is simpler to implement reliably (reuses a function you already know), while the heap approach is more extensible to streaming inputs. Start with the divide-and-conquer to get the correct answer, then discuss the heap optimization. Always handle empty lists and null nodes explicitly.
Common mistakes
- Naively merging lists one by one — O(kN) time, much worse than O(N log k).
- Inserting null nodes into the heap — always check node.next !== null before pushing.
- Not handling empty lists array or lists of empty linked lists as edge cases.
- In divide-and-conquer, not checking that i + interval < lists.length before reading lists[i + interval].
Follow-up questions
An interviewer at HP may pivot to one of these next:
- What if k is so large that the heap doesn't fit in memory — stream the input?
- Merge k sorted arrays (not linked lists) — does the heap approach still apply?
- How would you parallelize the divide-and-conquer merges across multiple threads?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is the heap approach O(N log k) and not O(N log N)?
The heap contains at most k elements at any time. Each of N extract-min operations costs O(log k), giving O(N log k) total. Since k ≤ N, log k ≤ log N — but often k << N in practice.
What does 'interval' represent in the divide-and-conquer version?
It tracks the merge distance. In round 1 (interval=1), we merge pairs (0,1), (2,3), etc. In round 2 (interval=2), we merge (0,2), (4,6), etc. After log k rounds, lists[0] holds the full result.
Does the divide-and-conquer version mutate the input array?
Yes — lists[i] is overwritten with the merged result at each step. If the input must be preserved, make a copy first.
Practice these live with InterviewChamp.AI
Drill Merge K Sorted Lists and other HP interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →