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 item) {
    Node *ptr, *temp;
    temp = new Node;
    temp->data = item;
    temp->next = NULL;
    if (*root == NULL) {
        *root = temp;
    }
    else {
        ptr = *root;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
}
void printLinkedList(Node* root) {
    while (root != NULL) {
        cout << root->data << " -> ";
        root = root->next;
    }
    cout << "NULL" << endl;
}
Node* generateNewLinkedList(Node* root1, Node* root2) {
    Node *ptr1 = root1, *ptr2 = root2;
    Node* root = NULL;
    while (ptr1 != NULL) {
        int currentMax = ((ptr1->data < ptr2->data) ? ptr2->data : ptr1->data);
        if (root == NULL) {
            Node* temp = new Node;
            temp->data = currentMax;
            temp->next = NULL;
            root = temp;
        }
        else {
            insertNewNode(&root, currentMax);
        }
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return root;
}
int main() {
    Node *root1 = NULL, *root2 = NULL, *root = NULL;
    insertNewNode(&root1, 1);
    insertNewNode(&root1, 2);
    insertNewNode(&root1, 3);
    insertNewNode(&root1, 4);
    insertNewNode(&root2, 3);
    insertNewNode(&root2, 1);
    insertNewNode(&root2, 2);
    insertNewNode(&root2, 4);
    root = generateNewLinkedList(root1, root2);
    printLinkedList(root);
    return 0;
}

コードのポイント

• insertNewNode関数：リストの末尾に新しいノードを追加します。二重ポインタを使うことで、空リストの場合も統一的に扱えます。
• generateNewLinkedList関数：2つのリストを同時に走査しながら、三項演算子で各位置の最大値を求め、新しいリストを構築します。
• 計算量：リストの長さをNとすると、末尾への挿入を毎回線形探索で行うため全体の計算量はO(N²)です。末尾ポインタを保持すればO(N)に改善できます。

実行結果

上記のコードを実行すると、次の出力が得られます。

3 -> 2 -> 3 -> 4 -> NULL

入力した2つのリスト「1 -> 2 -> 3 -> 4」と「3 -> 1 -> 2 -> 4」の各位置を比較すると、(1,3)→3、(2,1)→2、(3,2)→3、(4,4)→4となり、期待どおりの結果になっていることがわかります。

まとめ

本記事では、同じサイズの2つの連結リストから、各位置の最大値を取り出して新しい連結リストを生成するC++プログラムを紹介しました。連結リストの基本的な操作（挿入・走査・出力）の復習にも最適な題材です。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。