# 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列
以下错误的选项是？
## aop
### before
```cpp
#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
```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 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;
}
};
```