My confusion with these kinds of problems is whether or not a whole new Linked List must be created.
The first time I solved this problem, I used a modified approach to the merge 2 sorted lists problem.
The second time I solved this problem, priority queue came to my mind because the lists are already sorted.
What mistakes did I make?
- I inserted all the nodes in all the lists in to the priority queue. This is not needed. The size of the priority queue should be at most
kfor an optimal solution.
- I did not check the input for
NULLbefore inserting nodes in to the priority queue.
The time complexity is
O(N log(k)) where
N is the total number of nodes and
k is the number of Linked Lists. Inserting and removing from the priority queue is a
log(k) operation which is done
The space complexity is
O(N + k) or
k is much smaller than
The problem is taken from Leetcode.
Solution is hosted on Github.