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.

	ListNode *mergeKLists(vector<ListNode *> &lists) {
	ListNode* p = NULL;
	if(lists.size()<=0) return p;
	p= lists[0];
	for(int i=1; i<lists.size(); i++){
	p = mergeTwoLists(p, lists[i]);
	}
	return p;
	}
	ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
	if(!l1) return l2;
	if(!l2) return l1;
	ListNode *head = new ListNode(0);
	ListNode *pre = head;
	while(l1&&l2){
	if(l1->val < l2->val){
	pre->next = l1;
	pre = pre->next;
	l1 = l1->next;
	}
	else{
	pre->next = l2;
	pre = pre->next;
	l2 = l2->next;
	}
	}
	if(!l1) pre->next = l2;
	if(!l2) pre->next = l1;
	delete head;
	return head->next;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

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).

	Java:
	public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
	if(lists.size()==0) return null;
	PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>()
	{ public int compare(ListNode a, ListNode b){
	return a.val>b.val?1:(a.val==b.val?0:-1);
	}
	});
	for(ListNode list:lists){
	if(list!=null) q.add(list);
	}
	ListNode head = new ListNode(0), prev = head;
	while(q.size()!=0){
	ListNode temp = q.poll();
	prev.next = temp;
	if(temp.next!=null) q.add(temp.next);
	prev = prev.next;
	}
	return head.next;
	}
	}
	C++:
	class CompareListNode {
	public:
	bool operator()(ListNode *n1, ListNode *n2) // Returns true if t1 is earlier than t2
	{
	if (n1->val >= n2->val)
	return true;
	else
	return false;
	}
	};
	class Solution {
	public:
	ListNode *mergeKLists(vector<ListNode *> &lists) {.
	priority_queue<ListNode *, vector<ListNode *>, CompareListNode> q;
	for (const auto &list : lists) {
	if (list != NULL) {
	q.push(list);
	}
	}
	ListNode *head = new ListNode(0);;
	ListNode *curr = head;
	while (q.size() > 0) {
	ListNode *temp = q.top();
	curr->next = temp;
	curr = curr->next;
	q.pop();
	if (temp->next != NULL) {
	q.push(temp->next);
	}
	}
	curr = head->next;
	delete head;
	return curr;
	}
	};

view raw gistfile1.cpp hosted with ❤ by GitHub