题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解法一：
非递归解
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;
}
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10052215.html
