1 题目
题目：合并k个排序链表（Merge K Sorted Lists）
描述：合并 k 个排序链表（序列为升序序列），并且返回合并后的排序链表（序列为升序学列）。尝试分析和描述其复杂度。
lintcode题号——104，难度——medium
样例1：
输入：lists = [2->4->null,null,-1->null]
输出：-1->2->4->null
解释：将2->4->null、null和-1->null合并成一个升序的链表。
样例2：
输入：lists = [2->6->null,5->null,7->null]
输出：2->5->6->7->null
解释：将2->6->null、5->null和7->null合并成一个升序的链表。
2 解决方案
2.1 思路
??考虑使用多路归并算法，通过优先序列来解，将所有的链表头节点放入优先序列，选出最小节点并弹出，再不断加入后续的节点并弹出最小节点，直到所有节点都处理完成，弹出的节点顺序即为需要的排序顺序。
2.2 时间复杂度
??将n个节点加入容量k的优先序列的耗时O(n * log k)，弹出n个节点的耗时O(n * log k)，所以总的时间复杂度为O(n * log k)。
2.3 空间复杂度
??使用了容量为k的优先序列，所以空间复杂度为O(k)。
3 源码
细节：
- 使用优先序列的方式，需要先建立以
ListNode *为基础元素的最小堆优先序列。 - 将各个链表头节点加入优先序列，注意有效性（非空）的判断。
- 弹出最小节点，并加入该节点的下一个节点。
- 直到堆为空，弹出的节点组成的链表即为排好序的结果。
对自定义类型的优先序列构建的方式，需要自己编写比较函数：
auto cmp = [](ListNode * left, ListNode * right){return left->val > right->val;}; priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> > numQueue(cmp); // 建立最小堆优先序列
C++版本：
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
ListNode dummyNode(0);
if (lists.empty())
{
return nullptr;
}
auto cmp = [](ListNode * left, ListNode * right){return left->val > right->val;};
priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> numQueue(cmp); // 建立最小堆优先序列
for (auto it : lists)
{
if (it != nullptr)
{
numQueue.push(it);
}
}
ListNode * cur = &dummyNode;
while (!numQueue.empty())
{
ListNode * minNode = numQueue.top();
cur->next = minNode; // 将最小值接在cur之后
cur = cur->next; // cur向后移动一位
numQueue.pop();
if (minNode->next != nullptr)
{
numQueue.push(minNode->next); // 向优先序列放入弹出节点的链表中的后一个节点
}
}
return dummyNode.next;
}
