剑指Offer 合并两个排序的链表

题目描述

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

思路：

用2个新节点，一个用来存放新链表的头节点，另一个用来移动。当p1，p2有一个到尾部的时候，结束循环，讲另一条链剩下的插到新链尾部。

注意：需要考虑链表p1，p2为空的情况。

AC代码：

 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&&!pHead2)
14             return NULL;
15         if(!pHead1)
16             return pHead2;
17         if(!pHead2)
18             return pHead1;
19         
20         
21         ListNode *root=new ListNode(0);
22         ListNode *r=root;
23             
24         
25         while(pHead1&&pHead2)
26         {
27 
28             if(pHead1->val<pHead2->val)
29             {
30                 r->next=pHead1;
31                 pHead1=pHead1->next;
32             }
33             else
34             {
35                 r->next=pHead2;
36                 pHead2=pHead2->next;                
37             }
38             
39             r=r->next;                        
40         }
41         
42         if(pHead1)
43             r->next=pHead1;
44         if(pHead2)
45             r->next=pHead2;        
46         
47         return root->next;
48         
49     }
50 };