solution.md

# 合并K个升序链表

<p>给你一个链表数组，每个链表都已经按升序排列。</p><p>请你将所有链表合并到一个升序链表中，返回合并后的链表。</p><p>&nbsp;</p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>lists = [[1,4,5],[1,3,4],[2,6]]<strong><br />输出：</strong>[1,1,2,3,4,4,5,6]<strong><br />解释：</strong>链表数组如下：[  1-&gt;4-&gt;5,  1-&gt;3-&gt;4,  2-&gt;6]将它们合并到一个有序链表中得到。1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>lists = []<strong><br />输出：</strong>[]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>lists = [[]]<strong><br />输出：</strong>[]</pre><p>&nbsp;</p><p><strong>提示：</strong></p><ul>	<li><code>k == lists.length</code></li>	<li><code>0 &lt;= k &lt;= 10^4</code></li>	<li><code>0 &lt;= lists[i].length &lt;= 500</code></li>	<li><code>-10^4 &lt;= lists[i][j] &lt;= 10^4</code></li>	<li><code>lists[i]</code> 按 <strong>升序</strong> 排列</li>	<li><code>lists[i].length</code> 的总和不超过 <code>10^4</code></li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
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

```cpp
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<ListNode *> lists = {L1, L2, L3};

    ret = sol.mergeKLists(lists);

    ListNode *p = ret->next;

    while (p != NULL)
    {
        cout << p->val << " ";
        p = p->next;
    }
    return 0;
}
```

## 答案

```cpp
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> 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

```cpp
class Solution
{
public:
    struct Status
    {
        int val;
        ListNode *ptr;

        bool operator<(const Status &rhs) const
        {
            return val > rhs.val;
        }
    };

    priority_queue<Status> q;

    ListNode *mergeKLists(vector<ListNode *> &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

```cpp
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<ListNode *> &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

```cpp
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<ListNode *> &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];
    }
};
```