LeetCode: Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Analysis:

The key of this problem is to analyze its complexity. Suppose the average number of nodes in all list is n

Solution1: Loop over the heads of all list and find the smallest one and add it to the final list. The worst case is O(k*kn), because you have to compare k times to get a smallest node and there are kn nodes in total.

Solution2: first merge all lists one by one as follows. The worst case is O(kn) because you only need to compare once to get a valid node for the final list.



Solution3: Use a Priority Queue. About the complexity of building a priority queue with an array, a linked list, a BST, or a Heap, please see
http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html. The worst case is O(kn*logk). Here in the code notice that after you pop out a node node from the priority queue, you push node->next into the PQ; Therefore, the maximum number of nodes in the PQ is k and the insertion and deletion is both in O(logk).

Heap (minHeap):
For the insert operation, we start by adding a value to the end of the array (constant time, assuming the array doesn't have to be expanded); then we swap values up the tree until the order property has been restored. In the worst case, we follow a path all the way from a leaf to the root (i.e., the work we do is proportional to the height of the tree). Because a heap is a balanced binary tree, the height of the tree is O(log N), where N is the number of values stored in the tree. The removeMin operation is similar: in the worst case, we follow a path down the tree from the root to a leaf. Again, the worst-case time is O(log N).