题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：
用2个新节点，一个用来存放新链表的头节点，另一个用来移动。当p1，p2有一个到尾部的时候，结束循环，讲另一条链剩下的插到新链尾部。
注意：需要考虑链表p1，p2为空的情况。
AC代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(!pHead1&&!pHead2)
return NULL;
if(!pHead1)
return pHead2;
if(!pHead2)
return pHead1; ListNode *root=new ListNode();
ListNode *r=root; while(pHead1&&pHead2)
{ if(pHead1->val<pHead2->val)
{
r->next=pHead1;
pHead1=pHead1->next;
}
else
{
r->next=pHead2;
pHead2=pHead2->next;
} r=r->next;
} if(pHead1)
r->next=pHead1;
if(pHead2)
r->next=pHead2; return root->next; }
};