题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
（1）递归版本
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(nullptr == pHead1) return pHead2; if(nullptr == pHead2) return pHead1; if(pHead1->val > pHead2->val) { pHead2->next = Merge(pHead1,pHead2->next); return pHead2; } else { pHead1->next = Merge(pHead1->next,pHead2); return pHead1; } } };（2）非递归版本
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { //非递归 if(nullptr == pHead1 && nullptr == pHead2) return nullptr; ListNode * pHead = new ListNode(0); ListNode * cur = pHead ; while(true) { if(nullptr == pHead1) { cur->next =pHead2; break; } else if(nullptr == pHead2) { cur->next = pHead1; break; } if(pHead1->val > pHead2->val) swap(pHead1, pHead2); cur->next = pHead1; cur = cur->next; pHead1 = pHead1->next; } return pHead->next; } };点击练习：合并两个排序的链表
