leetcode23. 合并K个排序链表

题目链接

题意：给你k个有序链表，要对它们合为一个有序链表。

记得以前讲过这题，用重建法，时间复杂度为O(k*n)  , 空间复杂度为O(n)；

 

用最小堆优化：时间复杂度变为O(n*log(k))

class Solution{
public:
	struct cmp{
		bool operator()(ListNode *a, ListNode *b){
			return a->val > b->val;
		}
	};
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode*, vector<ListNode*>, cmp> pri_queue;
		for (auto elem : lists){
			if (elem) pri_queue.push(elem);
		}//for

		ListNode dummy;
		ListNode *p = &dummy;//哨兵结点
		ListNode *top;
		while (!pri_queue.empty()){
			top = pri_queue.top();
			pri_queue.pop();
			p->next = top;
			p = top;
			if (top->next) pri_queue.push(top->next);
		}//while
		return dummy.next;
	}
};