leetcode: Merge k Sorted Lists

Problem Description:

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

Solution and Precautions:

Very similar to the classical merge sort for two sorted arrays, since the k linked list are already sorted, we just find the smallest number among the heads list[i][0] (i=0,…k-1), of course, if some list already reached to the end, that is list[i][0] is NULL, we just ignore this list, the smallest number is obviously the smallest one in the combined or merged final list, we repeat this process and push the smallest number found into the tail of the final merger list until there is no elements left. To fast find the smallest number among the k head elements, we could adopt the heap data structure, thus each found and delete of the minHeap, it cost O(log k), and it is possible to perform n such operations where n is the total number of elements of the k list, thus the time complexity is bounded by O(n * log k).

Note, the bound could be even tighter since the size of the heap could be smaller when some list is consumed up. So for the delete min operations later on it might cost less than log k. (The exact bound is not easy to figure out for me) . The following is the accepted source code with heap, I personally consider it is quite elegant, any comments are welcome!

class mycomparison
	bool operator() (const ListNode * lhs, const ListNode *rhs) const
		return lhs->val > rhs->val;

class Solution {
    ListNode *mergeKLists(vector<ListNode *> &lists) {
		ListNode node(0);
		ListNode *current(&node);
		ListNode *ptr(NULL);

		priority_queue< ListNode *, vector<ListNode *>, mycomparison> heap;
		int k = lists.size();
		for (int i = 0; i < k; ++i) {
			if (lists[i]) heap.push(lists[i]);
		while (!heap.empty()) {
			ptr = current->next = heap.top();
			ptr = ptr->next;
			if (ptr) heap.push(ptr);
			current = current->next;
			current->next = NULL;
		return node.next;

Tips and Divergent thinking:

(1) If we following the normal way to merge these k sorted list by merging two list at a time, one small trick to make it faster is that sort the shorter list first (think about why?)
(2) I saw another solution to copy all the elements (total number of all the k lists is n) out (O(n) time) and sort them O(n log n time) and use these sorted elements to make a new list or just use the original nodes to build the sorted list (another O(n) time), this approach costs O(n log n) time, this is just another way to think about this problem although it might not hit the key point of this problem.

Written on May 6, 2013