题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
原理
通过递归：
A和B两个链表，每次比较A当前节点和B当前节点，如果A.val < B.val，就保留A的前节点，然后用l1的下一个节点开始的集合和B做合并，合并好的结果保存到nHead，这样即能保证小的节点排在前面，又能保证节点能串接在一起成为个大集合
反之，B.val < A.val也一样，先保留B当前节点，然后用B的下一个节点开始的集合和A合并，合并结果保存到B的下一个节点
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x, ListNode* ptr = nullptr) :
val(x), next(ptr)
{}
};
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr && pHead2 == nullptr)
return nullptr;
if (pHead1 == nullptr)
return pHead2;
if (pHead2 == nullptr)
return pHead1;
ListNode* nHead = nullptr;
if (pHead1->val <= pHead2->val)
{
nHead = pHead1;
nHead->next = Merge(pHead1->next, pHead2);
}
else
{
nHead = pHead2;
nHead->next = Merge(pHead1, pHead2->next);
}
return nHead;
}
|
输入为
输出为
