输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
再做这道题就是想不起来书上怎么做的了，但是最近看STL里面全是这种基础的合并啊，比较啊。就算不会也看会了。
循环我用了4个指针。p和q分别指向两个链表当前需要比较的元素，l和k分别代表“新”的链表的旧节点和新节点，防止断了。
每次新比较的结果给k，l代表之前的节点。
循环：
/*
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||pHead2==NULL){
if(pHead2==NULL)
return pHead1;
else return pHead2;}
ListNode *p=pHead1,*q=pHead2;
pHead1= pHead1->val<pHead2->val? pHead1:pHead2;
ListNode *k=pHead1,*l=pHead1;
while(p!=NULL&&q!=NULL){
if(p->val < q->val){
k=p;
p=p->next;
}
else {
k=q;
q=q->next;
}
l->next=k;
l=k;
}
if(q==NULL)
l->next=p;
if(p==NULL)
l->next=q;
return pHead1;
}
};
递归：
public class Solution {
public ListNode Merge(ListNode list1, ListNode list2) {
if(list1==null)
return list2;
else if(list2==null)
return list1;
ListNode mergeHead=null;
if(list1.val<list2.val){
mergeHead=list1;
mergeHead.next=Merge(list1.next, list2);
}
else{
mergeHead=list2;
mergeHead.next=Merge(list1, list2.next);
}
return mergeHead;
}
}