Description
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Discussion
合并k个有序的链表。最直观的方法自然先合并前两个1和2，再合并12和3，再合并123和4……但是这样的话效率并不高。因为每次要比较的链表长度呈直线上升。
更好的方法是分而治之。例如有8个链表，首先合并1和5，2和6，3和7，4和8，再合并15和26，37和48，再合并1526和3748。
另一种方法是利用最小堆。开始时将k个链表的表头元素取出构建一个最小堆，然后取出堆顶元素作为新链表的第一个元素，从该元素原属链表中取出一个元素加入最小堆，循环执行……
两种算法的时间复杂度都是O(nklogk)。
C++ Code
分治法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if(n == 0)
{
return NULL;
}
//按照分治法，两两合并
while(n > 1)
{
for(int i = 0; i < n / 2; i++)
{
lists[i] = mergeTwoLists(lists[i], lists[i + (n + 1) / 2]);
}
n = (n + 1) / 2;
}
return lists[0];
}
//第21题代码，hhh
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode * answer = new ListNode(0);
ListNode * tmp = answer;
while(l1 && l2)
{
if(l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
tmp->next = (l1? l1 : l2);
return answer->next;
}
};
最小堆法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//定义一个数据结构，用优先队列生成最小堆
struct cmp{
bool operator()(ListNode * a, ListNode * b){
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode *, vector<ListNode *>, cmp> pq;
int n = lists.size();
for(int i = 0; i < n; i++)
{
if(lists[i] != NULL)
{
pq.push(lists[i]);
}
}
ListNode * answer = NULL, * min = NULL, * pre = NULL;
while(pq.size() != 0)
{
min = pq.top();
pq.pop();
if(answer == NULL)
{
answer = min;
pre = min;
}
else
{
pre->next = min;
pre = pre->next;
}
if(pre->next != NULL)
{
pq.push(pre->next);
}
}
return answer;
}
};