剑指offer 16. 合并两个有序链表

16. 合并两个有序链表

题目描述

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

/*struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/

 1 class Solution {
 2 public:
 3     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 4     {
 5         ListNode* head = new ListNode(0);
 6         ListNode* cur = head;
 7         while(pHead1 != NULL && pHead2 != NULL){
 8             if(pHead1->val <= pHead2->val){
 9                 cur->next = pHead1;        // 指向这个结点
10                 pHead1 = pHead1->next;     // 头指针后移
11                 
12             }else if(pHead1->val > pHead2->val){
13                 cur->next = pHead2;
14                 pHead2 = pHead2->next;
15             }
16             cur = cur->next;        // cur指针后移
17         }
18         
19         // 如果有链表仍有元素，那么直接等于对应的头指针
20         if(pHead1)
21             cur->next = pHead1;
22         if(pHead2)
23             cur->next = pHead2;
24         
25         return head->next;
26     }
27 };