合并两个排序的链表

【题目描述】

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

【解题思路】

当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的节点依然是排序的，其后续的处理步骤与上述相同，因此可以考虑递归的思路：我们可以定义一个递归函数来实现后续的归并过程。

一旦输入空的链表就会引入空的指针，因此我们需要对空链表单独处理。当第一个链表是空链表，也就是它的头节点是一个空指针时，那么把它和第二个链表合并，合并之后的结果就是第二个链表；当第二个链表是空链表，把它和第一个链表合并，合并之后的结果是第一个链表。

【代码实现】

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12     {
13         if(pHead1==NULL)
14             return pHead2;
15         else if(pHead2==NULL)
16             return pHead1;
17 
18         ListNode * pNode1=pHead1;//尽量不在原来的指针上进行改动
19         ListNode * pNode2=pHead2;       
20         ListNode *pMergeHead=NULL;
21         if(pNode1->val<pNode2->val)
22         {
23             pMergeHead=pNode1;
24             pMergeHead->next=Merge(pNode1->next,pNode2);
25         }else
26         {
27             pMergeHead=pNode2;
28             pMergeHead->next=Merge(pNode1,pNode2->next);
29         }
30 
31         return pMergeHead;
32 
33     }
34 };