剣はOffer--017-を指して2つの並べ替えのチェーン時計を合併します

リンク
牛客OJ:2つのソートされたチェーンテーブルをマージ
9度OJ:http://ac.jobdu.com/problem.php?pid=1519
GitHubコード:017-2つのソートされたチェーンテーブルをマージ
CSDN題解:剣指Offer–017-合併2つのソートチェーンテーブル
牛客OJ
9度OJ
CSDN問題解
GitHubコード
2つのソートされたチェーンテーブルをマージ
1519-2つのソートされたチェーンテーブルをマージ
剣指Offer–017-2つのソートされたチェーンテーブルをマージ
017-2つのソートされたチェーンテーブルをマージ
実はこの問題はLeetCodeの前の問題と同じです.
LeetCodet問題解–21.Merge Two Sorted Lists(並べ替えられたチェーンテーブルを2つマージ)
もちろん彼には変種がたくさんあります.例えば、2つのチェーンテーブルがK個に拡張されたとき
LeetCodet問題解–23.Merge k Sorted Lists(K個の並べ替えられたチェーンテーブルをマージ)
に言及
タイトルの説明
2つの単調に増加したチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.
サンプル入力
1 3 5 7 9 2 4
サンプル出力
1 2 3 4 5 7 9
一般的な書き方
考え方は簡単で、2つのポインタで同期して2つのチェーンテーブルを巡り、小さなものを見つけるたびに新しいチェーンテーブルに挿入します.

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


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

#endif // __tmain

class Solution
{
public:
    ListNode* Merge(ListNode *pLeft, ListNode *pRight)
    {

        if(pLeft == NULL)
        {
            debug <<"left list is NULL" <<endl;
            return pRight;
        }
        else if(pRight == NULL)
        {
            debug <<"right list is NULL" <<endl;
            return pLeft;
        }

        ListNode *left = pLeft;
        ListNode *right = pRight;

        //       
        ListNode *head = NULL;
        if(left->val < right->val)
        {
            head = left;
            left = left->next;
            debug <<head->val <<"in list" <<endl;
        }
        else
        {
            head = right;
            right = right->next;
            debug <<head->val <<"in list" <<endl;
        }

        //       
        ListNode *curr = head;

        while(left != NULL && right != NULL)
        {
            //               
            debug <<"left = " <<left->val <<", right = " <<right->val <<endl;

            if(left->val < right->val)
            {
                debug <<left->val <<"in list" <<endl;

                curr->next = left;
                curr = curr->next;

                left = left->next;
            }
            else
            {
                debug <<right->val <<"in list" <<endl;

                curr->next = right;
                curr = curr->next;

                right = right->next;
            }
        }

        //            
        if(left != NULL)
        {
            curr->next = left;
        }
        else
        {
            curr->next = right;
        }


        return head;

    }
};

int __tmain( )
{
    ListNode left, right[3];

    left.val = 5;
    left.next = NULL;

    right[0].val = 1;
    right[0].next = &right[1];
    right[1].val = 2;
    right[1].next = &right[2];
    right[2].val = 4;
    right[2].next = NULL;


    Solution solu;
    ListNode *head = solu.Merge(&left, right);
    while(head != NULL)
    {
        cout <<head->val;
        head = head->next;
    }


    return 0;
}

再帰的な実装
実際には,ノードを追加するたびに機械的に繰り返されるため,再帰的に実現できると考えられる.

class Solution
{
public:
    ListNode* Merge(ListNode *pLeft, ListNode *pRight)
    {

        if(pLeft == NULL)
        {
            debug <<"left list is NULL" <<endl;
            return pRight;
        }
        else if(pRight == NULL)
        {
            debug <<"right list is NULL" <<endl;
            return pLeft;
        }

        ListNode *head = NULL;

        if(pLeft->val < pRight->val)
        {
            head = pLeft;
            head->next = Merge(pLeft->next, pRight);
        }
        else
        {
            head = pRight;
            head->next = Merge(pLeft, pRight->next);
        }

        return head;
    }
};