题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/* 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 (pHead1==NULL)?pHead2:pHead1; ListNode* prehead=new ListNode(0); ListNode* begin1=pHead1; ListNode* begin2=pHead2; ListNode* cur=prehead; while(begin1&&begin2) { if(begin1->val<=begin2->val) { cur->next=begin1; cur=cur->next; begin1=begin1->next; } else { cur->next=begin2; cur=cur->next; begin2=begin2->next; } } if(!begin1) { cur->next=begin2; } else cur->next=begin1; return prehead->next; } };或者直接操作两个链表，思路比较复杂，但是可以有效减少赋值操作。复杂度更低
* 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 (pHead1==NULL)?pHead2:pHead1; ListNode* prehead=new ListNode(0); prehead->next=(pHead1->val>pHead2->val)?pHead2:pHead1; ListNode* begin1=prehead->next; ListNode* begin2=(pHead1->val>pHead2->val)?pHead1:pHead2; while(begin1&&begin2) { if(begin1->val<=begin2->val) { if(((begin1->next)&&(begin1->next->val>begin2->val))||!(begin1->next)) { ListNode* temp=begin1->next; begin1->next=begin2; begin1=temp; } else begin1=begin1->next; } else { if(((begin2->next)&&(begin2->next->val>=begin1->val))||!(begin2->next)) { ListNode* temp=begin2->next; begin2->next=begin1; begin2=temp; } else begin2=begin2->next; } } return prehead->next; } };