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

题目描述：

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

分析：

苦力活，使用两个指针分别指向未被合并的两个链表的首部，比较两个首部数值的大小，合并数值小的结点，并且指针后移指向新的首部。

最后到了某一个链表的尾部之后，将尾部连接另一链表未被合并部分的首部。

代码：

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