劍指offer——合并兩個排序的連結清單

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        else if(pHead2==nullptr)
            return pHead1;
        ListNode* p1L=pHead1;
        ListNode* p2L=pHead2;
        ListNode* newHead=nullptr;
        ListNode* pNode=nullptr;
        while(p1L&&p2L){
            if(p1L->val<p2L->val){
                if(newHead==nullptr){//first ListNode
                    newHead=p1L;
                    pNode=p1L;
                }
                else{
                    pNode->next=p1L;
                    pNode=pNode->next;
                }
                p1L=p1L->next;
            }else{
                if(newHead==nullptr){
                    newHead=p2L;
                    pNode=p2L;
                }else{
                    pNode->next=p2L;
                    pNode=pNode->next;
                }
                p2L=p2L->next;
            }
        }
        if(p1L){
            pNode->next=p1L;
        }
        if(p2L){
            pNode->next=p2L;
        }
        return newHead;
    }
};      

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        else if(pHead2==nullptr)
            return pHead1;
        ListNode* newHead=nullptr;
        if(pHead1->val<pHead2->val){
            newHead=pHead1;
            newHead->next=Merge(pHead1->next,pHead2);
        }else{
            newHead=pHead2;
            newHead->next=Merge(pHead1,pHead2->next);
        }
        return newHead;
    }
};