合并两个排序的链表
一、题目要求
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
二、我的思路
1、比较两个链表的头结点大小，哪个小就将其作为新链表的头结点；
2、依次比较两个链表节点的大小，将一个链表合并到另一个链表中；
3、合并完之后，剩余部分合并到新链表最后；
我的代码
/*
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
== NULL)
return pHead2;
if(pHead2
== NULL)
return pHead1;
ListNode
*head
= NULL;
if(pHead1
->val
<= pHead2
->val){
head
= pHead1;
pHead1
= pHead1
->next;
}
else{
head
= pHead2;
pHead2
= pHead2
->next;
}
ListNode
*p
= head;
while(pHead1
&& pHead2){
if(pHead1
->val
<= pHead2
->val){
p
->next
= pHead1;
pHead1
= pHead1
->next;
}
else{
p
->next
= pHead2;
pHead2
= pHead2
->next;
}
p
= p
->next;
}
if(pHead1) p
->next
= pHead1;
else if(pHead2) p
->next
= pHead2;
return head;
}
};