题目地址：
https://oj.leetcode.com/problems/merge-k-sorted-lists/
题目内容：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
方法：
用最小堆来做就可以了。第一轮将链表所有头结点插入堆中，当堆非空时，弹出一个结点加入输出链表，若该结点有后继结点，则后继结点入堆。
复杂度分析：
设有k个链表，每个链表有n个结点。
则堆的大小最多为k。
每个结点都要入一次堆并出一次堆，入堆的复杂度为lgk，出堆时为了维护堆的性质复杂度也是lgk
一共有k * n个结点
所以，总的复杂度为O(k * n * lgk)
如果简单粗暴直接堆排序，那么堆的大小就是k * n，入堆出堆的复杂度就是lg(k * n)，要大不少。
如果直接按归并排序那样简单粗暴的归并，那么每轮中获得获胜结点的复杂度是k，由于每轮只产生一个获胜结点，所以一共有 k * n轮，那么复杂度就是O(k * k * n)
AC代码：（直接手写heap，免得重载运算符）
class Solution {
class MergeHeap
{
public:
MergeHeap()
{
heap.push_back(NULL);
}
bool isEmpty()
{
return heap.size() <= ; // 0号元素永远为NULL
}
void insert(ListNode *tmp)
{
if (tmp == NULL)
return;
heap.push_back(tmp);
mergeInsert();
}
ListNode *pop()
{
if (this->isEmpty())
return NULL;
int last = heap.size() - ;
ListNode *tmp = heap[];
heap[] = heap[last];
heap.pop_back();
if (!this->isEmpty())
mergeDelete();
return tmp;
}
private:
vector<ListNode *> heap;
void mergeDelete(int start)
{
int last = heap.size() - ;
ListNode *tmp = heap[start];
int lchild = start * ;
int rchild = start * + ;
int target = ; // marked win sub-tree
if (lchild <= last && rchild <= last)
{
target = heap[rchild]->val > heap[lchild]->val ? lchild : rchild;
}
else if (lchild <= last)
{
target = lchild;
}
else if (rchild <= last)
target = rchild;
if (target)
{
if (heap[target]->val < heap[start]->val)
{
heap[start] = heap[target];
heap[target] = tmp;
mergeDelete(target);
}
}
}
void mergeInsert()
{
int last = heap.size() - ;
int pare = last / ;
while (pare != )
{
if (heap[pare]->val > heap[last]->val)
{
ListNode *tmp = heap[pare];
heap[pare] = heap[last];
heap[last] = tmp;
}
else
break;
last = pare;
pare /= ;
}
}
};
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
MergeHeap myheap;
int len = lists.size();
if (!len)
return NULL;
for (int i = ;i < len;i++)
myheap.insert(lists[i]);
ListNode *head = NULL;
ListNode *tmp = NULL;
ListNode *tail = NULL;
while (!myheap.isEmpty())
{
tmp = myheap.pop();
if (!head) // init output list.
{
head = tmp;
tail = tmp;
}
else
{
tail->next = tmp;
tail = tmp;
}
if (tmp->next)
{
myheap.insert(tmp->next);
}
}
return head;
}
};