合成链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则 

附：合并规则类似于插入排序

非递归： 

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1==NULL&&pHead2==NULL) { return NULL; } if(pHead1==NULL) return pHead2; if(pHead2==NULL) return pHead1; ListNode* p1=pHead1; ListNode* p2=pHead2; ListNode* head=NULL; ListNode* p=NULL; while(p1!=NULL&&p2!=NULL) { if(p1->val<p2->val) { if(head==NULL) { head=p=p1; } else { p->next=p1; p=p->next; } p1=p1->next; } else { if(head==NULL) { head=p=p2; } else { p->next=p2; p=p->next; } p2=p2->next; } } if(p1!=NULL) { p->next=p1; } else if(p2!=NULL) { p->next=p2; } return head; }

递归：

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1==NULL&&pHead2==NULL) { return NULL; } if(pHead1==NULL) { return pHead2; } if(pHead2==NULL) { return pHead1; } ListNode* p1=pHead1; ListNode* p2=pHead2; ListNode* Mer=NULL; if(p1->val>p2->val) { Mer=p2; Mer->next=Merge(p1,p2->next); } else { Mer=p1; Mer->next=Merge(p1->next,p2); } return Mer; }