You are given k sorted linked lists. Merge all of them into one sorted linked list.
For example, given lists [[1,4,5], [1,3,4], [2,6]], the merged result is [1,1,2,3,4,4,5,6].
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Think about how to efficiently pick the smallest element across all k lists at any given time.
- Hint 2
A min-heap (priority queue) can hold the head node of each list and always give you the smallest.
- Hint 3
Push the head of each list into a min-heap. Pop the smallest, add it to the result, and push that node's next element onto the heap. Repeat until the heap is empty.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.