[Leetcode Solution] Merge k Sorted Lists

Analysis 

• This is a problem not hard but interesting. Here we go and have a look.
• In order to merge k sort lists, there are many solutions.Time complexity analysed based on a simplified situation that that are n lists and each of them contains m elements.
• The first one came into mind is do it just like how to merge two lists in the merge sort. Each time compare the current element of all the lists. Find out the smallest one and insert it into result list. However this solution could be really slow because it is O(m^(n*m)) time complexity.
• Another solution is each time merge two lists, and then merge the result list with another one until no list. If so the time complexity is O(n*n*m). However if use binary merge that first we merge all the original lists into n/2 lists and then merge these n/2 lists into n/4 and so forth until only one list left. This could be more efficient.
• One straightforward solution is just store all the elements in a vector, and then sort them. It's simple but works with O((n*m)*log(n*m)).
• A good solution in theoretical perspective is that we can maintain a priority queue with m elements. Each time we pop up the smallest element in the priority queue in O(1) time and then push in the element which is the next node of the popped one in O(log(m)) time. The overall time complexity is O((n*m)*log(m)). It should be faster then the above algorithm however in fact it is a little slower then the above one which may because it has a bigger coefficient.

Note 

• The signature of priority_queue constructor in C++ STL found here

• The difference between comparison parameter for priority_queue and for sort found here

• operator () found here
• const qualifier found here

Code