solution.md

# 合并两个有序链表

<p>将两个升序链表合并为一个新的 <strong>升序</strong> 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 </p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0021.Merge%20Two%20Sorted%20Lists/images/merge_ex1.jpg" style="width: 662px; height: 302px;" /><pre><strong>输入：</strong>l1 = [1,2,4], l2 = [1,3,4]<strong><br />输出：</strong>[1,1,2,3,4,4]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>l1 = [], l2 = []<strong><br />输出：</strong>[]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>l1 = [], l2 = [0]<strong><br />输出：</strong>[0]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li>两个链表的节点数目范围是 <code>[0, 50]</code></li>	<li><code>-100 <= Node.val <= 100</code></li>	<li><code>l1</code> 和 <code>l2</code> 均按 <strong>非递减顺序</strong> 排列</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(2);
    ListNode *l13 = new ListNode(4);

    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 *ret = new ListNode;

    ret = sol.mergeTwoLists(L1, L2);
    ListNode *p = ret->next;

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

```

## 答案

```cpp
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (l1 == NULL)
            return l2;
        else if (l2 == NULL)
            return l1;
        else if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        l2 = l2->next;
        ListNode *h = new ListNode(0);
        ListNode *head = h;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                h->next = new ListNode(l1->val);
                h = h->next;
                l1 = l1->next;
            }
            else
            {
                h->next = new ListNode(l2->val);
                h = h->next;
                l2 = l2->next;
            }
        }
        if (l1)
        {
            while (l1)
            {
                h->next = new ListNode(l1->val);
                h = h->next;
                l1 = l1->next;
            }
        }
        else if (l2)
        {
            while (l2)
            {
                h->next = new ListNode(l2->val);
                h = h->next;
                l2 = l2->next;
            }
        }
        ListNode *ptrDelete = head;
        head = head->next;
        delete ptrDelete;
        return head;
    }
};
```

### B

```cpp
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (NULL == l1)
            return l2;
        if (NULL == l2)
            return l1;
        l1 = l1->next;

        ListNode *p1 = l1;
        ListNode *p2 = l2;

        ListNode *head = new ListNode(-1);
        ListNode *curNode = head;

        while (NULL != p1 && NULL != p2)
        {
            if (p1->val < p2->val)
            {
                curNode->next = p1;
                curNode = p1;
                p1 = p1->next;
            }
            else
            {
                curNode->next = p2;
                curNode = p2;
                p2 = p2->next;
            }
        }

        if (NULL != p1)
            curNode->next = p1;
        if (NULL != p2)
            curNode->next = p2;

        return head->next;
    }
};
```

### C

```cpp
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        vector<int> vec;
        l1 = l1->next;
        while (l1 != NULL)
        {
            vec.push_back(l1->val);
            l1 = l1->next;
        }
        while (l2 != NULL)
        {
            vec.push_back(l2->val);
            l2 = l2->next;
        }

        sort(vec.begin(), vec.end());
        auto head = new ListNode;
        auto cur = head;
        for (const auto &c : vec)
        {
            auto p = new ListNode(c);
            cur->next = p;
            cur = p;
        }
        return head->next;
    }
};
```