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的关键字，，排序、新建结点插入。这种情况对原list是否排好序没有要求。
排序时间复杂度可以做到O(N* log N )，提取关键字和新建结点的时间复杂度都为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;}};
没有了爱的语言，所有的文字都是乏味的
