C++で2つの連結リストから各ノードの最大値を持つ新しい連結リストを作成する方法

このチュートリアルでは、与えられた2つの連結リスト（リンクリスト）から新しい連結リストを作成するC++プログラムを紹介します。

同じサイズの2つの連結リストが与えられ、各位置のノード同士を比較して、大きい方の値を要素とする新しい連結リストを生成します。

それでは、問題を解くための手順を順番に見ていきましょう。

• ノード構造体（struct Node）を定義します。

• 同じサイズの連結リストを2つ作成します。

• 連結リストを先頭から走査し、以下の処理を行います。

  • 2つの連結リストの対応するノードから、大きい方の値を求めます。

  • その値を持つ新しいノードを作成します。

  • 新しいノードを新しい連結リストの末尾に追加します。

• 完成した新しい連結リストを出力します。

実装例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
void insertNewNode(Node** root, int data) {
    Node *ptr, *temp;
    temp = new Node;
    temp->data = data;
    temp->next = NULL;
    if (*root == NULL) {
        *root = temp;
    }
    else {
        ptr = *root;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
}
Node* getNewLinkedList(Node* root1, Node* root2) {
    Node *ptr1 = root1, *ptr2 = root2, *ptr;
    Node *root = NULL, *temp;
    while (ptr1 != NULL) {
        temp = new Node;
        temp->next = NULL;
        if (ptr1->data < ptr2->data) {
            temp->data = ptr2->data;
        }
        else {
            temp->data = ptr1->data;
        }
        if (root == NULL) {
            root = temp;
        }
        else {
            ptr = root;
            while (ptr->next != NULL) {
                ptr = ptr->next;
            }
            ptr->next = temp;
        }
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return root;
}
void printLinkedList(Node* root) {
    while (root != NULL) {
        cout << root->data << "->";
        root = root->next;
    }
    cout << "NULL" << endl;
}
int main() {
    Node *root1 = NULL, *root2 = NULL, *root = NULL;
    insertNewNode(&root1, 1);
    insertNewNode(&root1, 2);
    insertNewNode(&root1, 3);
    insertNewNode(&root1, 4);
    cout << "最初の連結リスト: ";
    printLinkedList(root1);
    insertNewNode(&root2, 0);
    insertNewNode(&root2, 5);
    insertNewNode(&root2, 2);
    insertNewNode(&root2, 6);
    cout << "2番目の連結リスト: ";
    printLinkedList(root2);
    root = getNewLinkedList(root1, root2);
    cout << "新しい連結リスト: ";
    printLinkedList(root);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次のような結果が出力されます。

最初の連結リスト: 1->2->3->4->NULL
2番目の連結リスト: 0->5->2->6->NULL
新しい連結リスト: 1->5->3->6->NULL

まとめ

このチュートリアルでは、同じサイズの2つの連結リストを同時に走査しながら、各位置で大きい方の値を選んで新しい連結リストを構築する方法を学びました。処理はリストの長さに対して線形時間 O(n) で完了するため、効率的なアルゴリズムです。連結リストの基本操作である挿入・走査・新規ノードの作成を一度に練習できる、非常に良い題材と言えます。

チュートリアルの内容について質問がある場合は、ぜひコメント欄でお知らせください。