题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
题解：
使用普通方法，或者递归，注意新的头节点即可。
//使用普通的合并方法
class Solution01 {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr || pHead2 == nullptr)return pHead1 == nullptr ? pHead2 : pHead1;
ListNode* newHead = nullptr, *p1 = nullptr, *p2 = nullptr;
newHead = new ListNode();
newHead->next = pHead1;
p1 = newHead;
p2 = pHead2;
while (p1->next != nullptr && p2 != nullptr)
{
if (p1->next->val < p2->val)
p1 = p1->next;
else
{
ListNode* temp = p1->next;
p1->next = p2;
p2 = p2->next;
p1->next->next = temp;
p1 = p1->next;
}
}
if (p1->next == nullptr && p2 != nullptr)
p1->next = p2;
return newHead->next;
}
}; //使用递归
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr || pHead2 == nullptr)return pHead1 == nullptr ? pHead2 : pHead1;
ListNode* newHead = nullptr;
if (pHead1->val < pHead2->val)
{
newHead = pHead1;
newHead->next = Merge(pHead1->next, pHead2);
}
else
{
newHead = pHead2;
newHead->next = Merge(pHead1, pHead2->next);
}
return newHead;
}
};