# 23. Merge K Sorted Lists 合并k个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Difficulty: Hard

### 解法1

``````/**
* 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;
ListNode* res = lists[0];
for (int i=1;i < n;i++){
ListNode* node = lists[i];
res = mergeTwoLists(res,node);
}
return res;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1==NULL) return l2;
if (l2==NULL) return l1;
ListNode* head = NULL;
if (l1->val<l2->val)
{
}
else
{
}
}
};
``````

### 解法2

``````/**
* 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) {
if (lists.size() == 0) return NULL;
int n = lists.size();
while (n > 1) {
int k = (n+1)/2;
for (int i = 0; i < n/2;i++)
lists[i] = mergeTwoLists(lists[i],lists[k+i]);
n = k;
}
return lists[0];
}
ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
if (l1==NULL) return l2;
if (l2==NULL) return l1;
ListNode* head = NULL;
if (l1->val<l2->val)
{
}
else
{
}
}
};
``````

### 解法3

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/

bool cmp (ListNode* a, ListNode* b)
{
if (a && b)
{
return a->val > b->val;
}
else if (!a) return false;
else return true;
}

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<ListNode*> min;
for (int i = 0; i < lists.size(); i++) {
min.push_back(lists[i]);
push_heap(min.begin(), min.end(), cmp);
}

ListNode* head = NULL,*pre = NULL,*top = NULL;
while (!min.empty())
{
top = min[0];
if (!top)
{
pop_heap(min.begin(), min.end(), cmp);
min.pop_back();
continue;
}
if (pre) pre->next = top;
pre = top;
pop_heap(min.begin(),min.end(),cmp);
min.pop_back();
if (top->next)
{
min.push_back(top->next);
push_heap(min.begin(), min.end(), cmp);
}
}
}
};
``````

``````priority_queue<Type,Container,Compare>

//  Type 为数据类型
//  Container 为保存数据的容器, 必须是用数组实现的容器，比如 vector, deque 但不能用list。STL里面默认用的是 vector
//  Compare为元素比较方式。. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

1,关于STL中的priority_queue:确定用top()查看顶部元素时,该元素是具有最高优先级的一个元素. 调用pop()删除之后,将促使下一个元素进入该位置.
2,如同stack和queue,priority_queue是一个基于基本序列容器进行构建的适配器,默认的序列器是vector.
``````
``````/**
* 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) {
if (a && b) return a->val > b->val;
return false;
}
};

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,cmp> q;
for (int i = 0; i < lists.size();i++)
{
if (lists[i]) q.push(lists[i]);
}
ListNode *head = NULL,*pre = NULL,*top = NULL;
while (!q.empty()) {
top = q.top();
q.pop();
if (!pre) head = top;
else pre->next = top;
pre = top;
if (top->next) q.push(top->next);
}