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

题目描述

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

思路

1. 声明 p, q 两个结点指针，分别指向两个链表的当前结点。
2. 声明 newHead, 新链表的头指针，newPnow 指向新链表的当前结点。
3. p q 两个结点指向的值互相比较，新链表的当前结点指向那个比较小的，之后互相向前移动。
4. 当有一个链表为空，直接将新链表当前结点的 next 指针指向另外一个链表，后面本身就是已经连着的。

代码

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* p, *q, *newHead = NULL, *newPNow;
        p = pHead1;
        q = pHead2;
        
        if(pHead1 == NULL)
            return pHead2;
        else if(pHead2 == NULL)
            return pHead1;
        
        while(p != NULL && q != NULL)
        {
            if(p->val >= q->val)
            {
                if(newHead == NULL)
                {
                    newHead = q;
                    newPNow = q;
                    q = q->next;
                }   
                else
                {
                    newPNow->next = q;
                    newPNow = q;
                    q = q->next;  
                }
            }
            else
            {
                if(newHead == NULL)
                {
                    newHead = p;
                    newPNow = p;
                    p = p->next;
                }
                else
                {
                    newPNow->next = p;
                    newPNow = p;
                    p = p->next;    
                }

            }
        }
        if(p == NULL)
        {
                newPNow->next = q; 
        }
        else if(q == NULL)
        {
                newPNow->next = p;
        }
        return newHead;
    }
};