剑指offer——合并两个排序的链表

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

方法一：根据归并排序思想。注意：pMergeHead头节点的指向；其中一支链表结束之后，另一支直接接到pCurrent之后即可；

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* pMergeHead = NULL; ListNode* pCurrent = NULL; ListNode* p1 = pHead1; ListNode* p2 = pHead2; if(!p1) return pHead2; if(!p2) return pHead1; while(p1 && p2) { if(p1->val < p2->val) { if(!pMergeHead){ pMergeHead = p1; pCurrent = pMergeHead; } else { pCurrent->next = p1; pCurrent = pCurrent->next; } p1 = p1->next; } else { if(!pMergeHead){ pMergeHead = p2; pCurrent = pMergeHead; } else { pCurrent->next = p2; pCurrent = pCurrent->next; } p2 = p2->next; } } if(p1){ pCurrent->next = p1; } else { pCurrent->next = p2; } return pMergeHead; } };

方法二：利用递归的思想

/* 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) return pHead2; if(!pHead2) return pHead1; if(pHead1->val < pHead2->val){ pHead1->next = Merge(pHead1->next, pHead2); return pHead1; } else { pHead2->next = Merge(pHead1, pHead2->next); return pHead2; } } };