23. Merge k Sorted Lists

题意：

给一堆已排序链表，合并成一个已排序链表
试了几个方法，最高的大概Runtime排行才71%，不过不知道这个runtime为什么每次都不一样，有的时候能到99%。。。还是我菜啊。

思路1：

就是和之前两个链表合并的思想一样，每次找所有链表里最大的头结点，移动。

ListNode* mergeKLists1(vector<ListNode*>& lists) {//19%
	vector<int> num;
	ListNode *res=NULL, *temp=NULL,*min_list;
	int sz = lists.size(), min_a,min_b;
	for (int i = 0; i < sz; ++i) {
		if (!lists[i]) {
			lists.erase(lists.begin() + i);
			--i;
			--sz;
		}
	}
	if (sz == 0)
		return NULL;
	for (int i = 0; i < sz; ++i)
		num.push_back(i);
	while (sz>1) {
		min_a = INT_MAX;
		for (int i = 0; i < sz; ++i) {
			if (min_a > lists[num[i]]->val) {
				min_list = lists[num[i]];
				min_a = min_list->val;
				min_b = i;
			}
		}
		if (!temp) {
			res = temp = min_list;
		}
		else {
			res->next = min_list;
			res = res->next;
		}
		lists[num[min_b]] = lists[num[min_b]]->next;
		if (!lists[num[min_b]]) { 
			num.erase(num.begin() + min_b); 
			sz--;
		}
	}
	if (res)
		res->next = lists[num[0]];
	else
		return lists[0];
	return temp;
}

思路2：

在思路1的基础上使用二分法优化

ListNode* MergeList(ListNode* a, ListNode*b) {
	if (!a) return b;
	if (!b) return a;
	if (a->val > b->val) swap(a, b);
	ListNode *res = a, *temp = a;
	a = a->next;
	while (a&&b) {
		if (a->val > b->val) {
			temp->next = b;
			temp = temp->next;
			b = b->next;
		}
		else {
			temp->next = a;
			temp = temp->next;
			a = a->next;
		}
	}
	if (a)
		temp->next = a;
	if (b)
		temp->next = b;
	return res;
}


ListNode* mergeKLists2(vector<ListNode*>& lists) {//52.59%
	int sz = lists.size();
	if (sz == 2)
		return MergeList(lists[0], lists[1]);
	if (sz == 1)
		return lists[0];
	if (sz == 0)
		return NULL;
	vector<ListNode*> L(lists.begin(), lists.begin() + sz / 2);
	vector<ListNode*> R(lists.begin() + sz / 2, lists.end());
	return MergeList(mergeKLists2(L), mergeKLists2(R));
}

思路三：

在1的基础上使用堆进行优化，将每个链表的头结点塞入大顶堆，取堆顶后连接在总链表后面再将取出结点的下一结点放入堆中。重复上述操作

ListNode* mergeKLists3(vector<ListNode*>& lists) {
	priority_queue< ListNode*, vector<ListNode*>, greater<int>> pq;
	for (auto l : lists)
		if (l)
			pq.push(l);
	ListNode *node, *head;
	head = NULL;
	while (!pq.empty()) {
		node = pq.top();
		pq.pop();
		if (!head)
			head = node;
		if (node->next)
			pq.push(node->next);
		node->next = pq.empty() ? NULL : pq.top;
	}
	return head;
}