C++で3つのリンクリストに共通する要素を効率的に検索する方法（ハッシュ活用）

3つのリンクリストが与えられたとき、それらすべてに共通して存在する要素を見つける問題を考えてみましょう。例えば、リストが [10, 12, 15, 20, 25]、[10, 12, 13, 15]、[10, 12, 15, 24, 25, 26] の3つである場合、共通する要素は 10、12、15 となります。

この問題はハッシュテーブル（ハッシュマップ）を使うことで効率的に解決できます。各要素の出現状況を「頻度カウント」として管理し、3つのリストすべてに出現した要素を特定する仕組みです。

アルゴリズムの手順

• ステップ1： 空のハッシュテーブルを作成します。最初のリンクリストを走査し、各要素をハッシュテーブルに挿入して頻度を「1」に設定します。
• ステップ2： 2番目のリンクリストを走査します。現在の要素がハッシュテーブルに存在し、その頻度が「1」であれば、「2」に更新します。
• ステップ3： 3番目のリンクリストを走査します。現在の要素の頻度が「2」であれば、「3」に更新します。これにより、3つのリストすべてに出現したことが記録されます。
• ステップ4： 最後にハッシュテーブルを確認し、頻度が「3」になっている要素を出力します。それらが求める共通要素です。

C++による実装例

#include<iostream>
#include<unordered_map>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

// リストの先頭にノードを追加する関数
void addNode(Node** start, int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = (*start);
    (*start) = newNode;
}

// 3つのリストに共通する要素を検索する関数
void findCommonValues(Node* list1, Node* list2, Node* list3) {
    unordered_map<int, int> hash;

    // 1つ目のリスト：頻度を1に設定
    Node* p = list1;
    while (p != NULL) {
        hash[p->data] = 1;
        p = p->next;
    }

    // 2つ目のリスト：既存要素の頻度を2に更新
    Node* q = list2;
    while (q != NULL) {
        if (hash.find(q->data) != hash.end())
            hash[q->data] = 2;
        q = q->next;
    }

    // 3つ目のリスト：頻度が2の要素を3に更新
    Node* r = list3;
    while (r != NULL) {
        if (hash.find(r->data) != hash.end() && hash[r->data] == 2)
            hash[r->data] = 3;
        r = r->next;
    }

    // 頻度が3の要素（= 共通要素）を出力
    for (auto x : hash) {
        if (x.second == 3)
            cout << x.first << " ";
    }
}

int main() {
    Node* list1 = NULL;
    addNode(&list1, 10);
    addNode(&list1, 12);
    addNode(&list1, 15);
    addNode(&list1, 20);
    addNode(&list1, 25);

    Node* list2 = NULL;
    addNode(&list2, 10);
    addNode(&list2, 12);
    addNode(&list2, 13);
    addNode(&list2, 15);

    Node* list3 = NULL;
    addNode(&list3, 10);
    addNode(&list3, 12);
    addNode(&list3, 15);
    addNode(&list3, 24);
    addNode(&list3, 25);
    addNode(&list3, 26);

    cout << "Common elements are: ";
    findCommonValues(list1, list2, list3);
}

実行結果

Common elements are: 10 12 15

計算量について

この手法の時間計算量は O(n₁ + n₂ + n₃) です。ここで n₁、n₂、n₃ はそれぞれのリンクリストの長さを表します。ハッシュテーブルへの挿入・検索は平均 O(1) で行えるため、全リストを一度ずつ走査するだけで済みます。空間計算量も O(n₁) と、最初のリストの要素数に依存する形で抑えられます。

なお、unordered_map を使用しているため、出力順序は実装によって異なる場合があります。ソートされた順序で結果が必要な場合は、map を使用するか、出力前にソートを行うことをおすすめします。