# 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
struct ListNode
{
int val;
struct ListNode *next;
ListNode() : val(0), next(nullptr){};
ListNode(int x) : val(x), next(nullptr){};
ListNode(int x, ListNode *next) : val(x), next(next){};
};
```
### after
```c
int main()
{
Solution sol;
ListNode *L1 = new ListNode;
ListNode *l11 = new ListNode(1);
ListNode *l12 = new ListNode(4);
ListNode *l13 = new ListNode(5);
L1->next = l11;
l11->next = l12;
l12->next = l13;
ListNode *L2 = new ListNode;
ListNode *l21 = new ListNode(1);
ListNode *l22 = new ListNode(3);
ListNode *l23 = new ListNode(4);
L2->next = l21;
l21->next = l22;
l22->next = l23;
ListNode *L3 = new ListNode;
ListNode *l31 = new ListNode(2);
ListNode *l32 = new ListNode(6);
L3->next = l31;
l31->next = l32;
ListNode *ret = new ListNode;
vector lists = {L1, L2, L3};
ret = sol.mergeKLists(lists);
ListNode *p = ret->next;
while (p != NULL)
{
cout << p->val << " ";
p = p->next;
}
return 0;
}
```
## 答案
```c
struct cmp
{
bool operator()(ListNode *a, ListNode *b)
{
return a->val > b->val;
}
};
class Solution
{
public:
ListNode *mergeKLists(vector &lists)
{
priority_queue, cmp> queue;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != NULL)
queue.push(lists[i]);
}
if (queue.empty())
return NULL;
ListNode *root = new ListNode(-1);
ListNode *node;
ListNode *lastNode = root;
while (!queue.empty())
{
node = queue.top();
queue.pop();
lastNode->next = node;
lastNode = lastNode->next;
if (node->next)
queue.push(node->next);
}
lastNode->next = NULL;
return root->next;
}
};
```
## 选项
### A
```c
class Solution
{
public:
struct Status
{
int val;
ListNode *ptr;
bool operator<(const Status &rhs) const
{
return val > rhs.val;
}
};
priority_queue q;
ListNode *mergeKLists(vector &lists)
{
for (int i = 0; i < lists.size() - 1; i++)
{
lists[i + 1] = lists[i + 1]->next;
}
for (auto node : lists)
{
if (node)
q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty())
{
auto f = q.top();
q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next)
q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
```
### B
```c
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
if (!l1 || !l2)
return l1 ? l1 : l2;
ListNode fake, *la = l1, *lb = l2;
ListNode *cur = &fake;
while (la && lb)
{
if (la->val < lb->val)
{
cur->next = la;
la = la->next;
}
else
{
cur->next = lb;
lb = lb->next;
}
cur = cur->next;
}
cur->next = la ? la : lb;
return fake.next;
}
ListNode *mergeKLists(vector &lists)
{
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i)
{
if (i >= 1)
lists[i] = lists[i]->next;
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};
```
### C
```c
class Solution
{
public:
ListNode *mergeTlists(ListNode *l1, ListNode *l2)
{
if (l1 == nullptr)
return l2;
else if (l2 == nullptr)
return l1;
else if (l1->val < l2->val)
{
l1->next = mergeTlists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTlists(l2->next, l1);
return l2;
}
}
ListNode *mergeKLists(vector &lists)
{
int len = lists.size();
if (len == 0)
return nullptr;
if (len == 1)
return lists[0];
for (int i = 0; i < len - 1; i++)
{
lists[i + 1] = lists[i + 1]->next;
lists[i + 1] = mergeTlists(lists[i], lists[i + 1]);
}
return lists[len - 1];
}
};
```