problem：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Tags Divide and Conquer Linked List Heap
合并K个已序单链表
thinking：
（1）题目没有要求不能够新开ListNode,所以暴力破解法：提取K个list的keyword。排序、新建结点插入。这样的情况对原list是否排好序没有要求。
排序时间复杂度能够做到O(N* log N )。提取keyword和新建结点的时间复杂度都为O（N），所以总的时间复杂度为O（N*logN），这没有考虑新建结点的时间浪费和空间 浪费。
（2）採用能够容纳结点的容器，想到的是堆，或者堆的封装-优先队列，因为堆的O(N*logN)排序的时间复杂度。并且不用新开结点，节省空间。
暴力法：
/**
* 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) {
ListNode *newlist=NULL;
vector<int> tem;
for(int i=0;i<lists.size();i++)
{
while(lists.at(i)!=NULL)
{
tem.push_back(lists.at(i)->val);
lists.at(i)=lists.at(i)->next;
}
}
if(tem.size()==0)
return NULL;
sort(tem.begin(),tem.end());
for(int i=tem.size()-1;i>=0;i--)
{
ListNode *p = new ListNode(tem.at(i));
p->next = newlist;
newlist = p;
}
return newlist;
}//mergeKLists()
};
优先队列法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class ListNodeCompare:public binary_function<ListNode*,ListNode*,bool>
{
public:
bool operator()(ListNode* t1,ListNode* t2)const
{
if ( !t1||!t2 )
return !t2;
return t1->val>t2->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (lists.empty())
return NULL;
priority_queue<ListNode*,vector<ListNode*>,ListNodeCompare> Q;
for(int i=0;i<lists.size();i++)
if ( lists[i]!=NULL)
Q.push(lists[i]);
ListNode guard(-1);
ListNode* tail=&guard;
while(!Q.empty())
{
ListNode* toAdd=Q.top();
Q.pop();
tail->next=toAdd;
tail=tail->next;
if (toAdd->next)
Q.push(toAdd->next);
}
return guard.next;
}
};