(剣指Offer)面接問題17:2つのソートされたチェーンテーブルをマージ

タイトル:
2つの増分ソートされたチェーンテーブルを入力し、2つのチェーンテーブルを結合し、新しいチェーンテーブルのノードを増分ソートします.
チェーンテーブルノードの定義は次のとおりです.

struct ListNode{
    int val;
    ListNode* next;
};

考え方:
2つのインクリメンタルソートされたチェーンテーブルをマージします.これは、集計ソートされたmergeプロセスに似ています.
1、両方のチェーンテーブルが空でない場合、
チェーンテーブル1のヘッダノードの値がチェーンテーブル2のヘッダノードの値より小さい場合、チェーンテーブル1のヘッダノードは新しいチェーンテーブルのヘッダノードとなり、そうでなければチェーンテーブル2のヘッダノードは新しいチェーンテーブルのヘッダノードとなり、チェーンテーブルポインタは一歩前進する.
2つのチェーンテーブルの残りのノードの動作を同期する.(これは再帰的なプロセスです)
2、2つのチェーンテーブルの少なくとも1つが空である場合、
新しいチェーンテーブルのポインタは空ではないものを指します.
コード:

struct ListNode{
    int val;
    ListNode* next;
};

// recursive method
ListNode* Merge_1(ListNode* pHead1, ListNode* pHead2){
    if(pHead1==NULL)
        return pHead2;
    if(pHead2==NULL)
        return pHead1;
    if(pHead1->val<pHead2->val){
        pHead1->next=Merge_1(pHead1->next,pHead2);
        return pHead1;
    }
    else{
        pHead2->next=Merge_1(pHead1,pHead2->next);
        return pHead2;
    }
}

// non-recursive method
ListNode* Merge_2(ListNode* pHead1, ListNode* pHead2){
    ListNode *p=new ListNode();
    ListNode *MergeHead=p;
    while(pHead1!=NULL && pHead2!=NULL){
        if(pHead1->val<pHead2->val){
            MergeHead->next=pHead1;
            pHead1=pHead1->next;
        }
        else{
            MergeHead->next=pHead2;
            pHead2=pHead2->next;
        }
        MergeHead=MergeHead->next;
    }

    if(pHead1==NULL)
        MergeHead->next=pHead2;
    if(pHead2==NULL)
        MergeHead->next=pHead1;

    return p->next;
}

オンラインテストOJ:
http://www.nowcoder.com/books/coding-interviews/d8b6b4358f774294a89de2a6ac4d9337?rp=1
ACコード:

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

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *p=new ListNode(0);
        ListNode *MergeHead=p;
        while(pHead1!=NULL && pHead2!=NULL){
            if(pHead1->val<pHead2->val){
                MergeHead->next=pHead1;
                pHead1=pHead1->next;
            }
            else{
                MergeHead->next=pHead2;
                pHead2=pHead2->next;
            }
            MergeHead=MergeHead->next;
        }

        if(pHead1==NULL)
            MergeHead->next=pHead2;
        if(pHead2==NULL)
            MergeHead->next=pHead1;

        return p->next;
    }
};