题目描述：

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

分析：

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

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

代码：

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 };