LeetCode Q23: Merge k Sorted Lists (Hard)

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

Solution 1:
The initial idea is very straightforward that every time we take the node with the least number from k lists and link this node to current merged list. To speed up in every round when choosing node with smallest number, I use priority queue.

The code is in following:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	struct compare {
	bool operator()(const ListNode* l, const ListNode* r) {
	return l->val > r->val;
	}
	};
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	ListNode* kLists=NULL;
	ListNode* kListsHead=NULL;
	int k=lists.size();
	int endCount=0;
	priority_queue<ListNode*, std::vector<ListNode*>, compare> heap;
	//fill priority queue
	for(int i=0; i<k; ++i){
	ListNode* p=lists[i];
	if(p!=NULL)
	heap.push(p);
	else
	endCount++;
	}
	while(endCount!=k){
	if(heap.empty())
	return kLists;
	ListNode* node=heap.top();
	heap.pop();
	if(kLists!=NULL){
	kLists->next=node;
	kLists=node;
	}else{
	kLists=node;
	kListsHead=kLists;
	}
	node=node->next;
	if(node==NULL){
	endCount++;
	continue;
	}else
	heap.push(node);
	}
	return kListsHead;
	}
	};

view raw Q23MergekSortedLists.cpp hosted with ❤ by GitHub

Solution 2:
Divide and conque, merge 2 lists at a time. Fastest, 36ms, beat 100%

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* p=NULL;
	if(l1==NULL)
	return l2;
	if(l2==NULL)
	return l1;
	if(l1->val<l2->val){
	p=l1;
	l1=l1->next;
	p->next=mergeTwoLists(l1, l2);
	}else{
	p=l2;
	l2=l2->next;
	p->next=mergeTwoLists(l1, l2);
	}
	return p;
	}
	ListNode* helper(vector<ListNode*>& lists, int s, int e){
	ListNode* res=NULL;
	if(s==e)
	return lists[s];
	if(e-s==1){
	res = mergeTwoLists(lists[s], lists[e]);
	return res;
	}
	int mid = (s+e)/2;
	ListNode* l1 = helper(lists, s, mid);
	ListNode* l2 = helper(lists, mid+1, e);
	res = mergeTwoLists(l1, l2);
	return res;
	}
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	ListNode* res=NULL;
	if(lists.empty())
	return res;
	res = helper(lists, 0, lists.size()-1);
	return res;
	}
	};

view raw Q23-2.cpp hosted with ❤ by GitHub