LeetCode_023: Merge k Sorted Lists

        一种结合链表和优先队列的优雅解法，巧妙之处在于使用优先队列出队元素，可以直接得到下一个入队元素，算法复杂度是O(nlgn)。联想到如果不是优先队列结构，那么我们可以使用同样的解法，只是我们需要在队列中记录每个元素属于哪一行，而使用链表结构就避免了这种麻烦。

题目

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

分析

如摘要中所说，最小元素一定是每一个链表最前面的元素之一，在其中选取最小的。那么，自然就是使用优先队列了。

另外，一个小技巧，代码中使用了哑节点，方便书写循环。

代码

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode *, vector<ListNode*>, cmp> q;
		for (auto l : lists){
			if (l){
				q.push(l);
			}
		}
		if (q.empty()){
			return NULL;
		}

		ListNode dummy(0);
		ListNode* node = &dummy;
		while (!q.empty()){
			node->next = q.top();
			q.pop();
			node = node->next;
			if (node->next){
				q.push(node->next);
			}
		}
		return dummy.next;
	}
	
private:
	struct cmp{
		bool operator()(const ListNode* l, const ListNode* r){
			return l->val > r->val;
		}
	};
};