题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解法一：
解法一：
非递归解
class Solution
{
public:
ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
{
if (pHead1 == NULL)
return pHead2;
if (pHead2 == NULL)
return pHead1;
ListNode *a = pHead1;
ListNode *b = pHead2;
ListNode *res = NULL;
ListNode *cur = NULL;
while (a != NULL && b != NULL)
{
if (a->val < b->val)
{
if (res == NULL)
{
res = cur = a;
}
else
{
cur->next = a;
cur = cur->next;
}
a = a->next;
}
else
{
if (res == NULL)
{
res = cur = b;
}
else
{
cur->next = b;
cur = cur->next;
}
b = b->next;
}
}
if (a == NULL)
cur->next = b;
else
cur->next = a;
return res;
}
};
解法二：
递归解
class Solution
{
public:
ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
{
if (pHead1 == NULL)
return pHead2;
if (pHead2 == NULL)
return pHead1;
if (pHead1->val < pHead2->val)
{
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}
else
{
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};