DSA interview question

Merge K Sorted Linked Lists

Hard · Data structures · Topics: heap, linkedlist, divide and conquer

The problem

A search engine gathers results from k shards, and each shard returns its hits as a sorted linked list by score. The front end needs one sorted list. Merging the lists one after another costs O(N · k) for N total nodes. A min-heap of the k current list heads always holds the next smallest node: pop it, append it to the output, and push its successor. That's O(N log k).

Example: [[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6].

Function signature

Node* mergeKLists(vector<Node*>& lists);  // each list sorted ascending; some may be empty

Test cases

Input	Output	Explanation
`[[1,4,5], [1,3,4], [2,6]]`	`[1, 1, 2, 3, 4, 4, 5, 6]`
`[]`	`[]`	No lists
`[[]]`	`[]`	One empty list
`[[2], [1]]`	`[1, 2]`
`[[1, 2, 3]]`	`[1, 2, 3]`

(Confirm: the lists are sorted ascending; reuse the existing nodes; N total nodes across k lists.)

How interviewers phrase it

"You are given an array of k linked lists, each sorted in ascending order. Merge all of them into one sorted linked list" (LeetCode 23).

Clarifying questions to ask

Can some lists be empty, or the array itself empty? (Yes.)
Reuse the nodes or create new ones? (Reuse.)
How large are k and N? (k up to 10⁴, N up to 10⁴.)

Follow-ups to expect

"Why does the heap hold only heads?"
"How do you order Node pointers in the heap?"
"Divide and conquer alternative?"
"Why is merging one by one slower?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview