C++で2つの片方向リンクリストに共通するノードを検索して数える方法

2つの片方向リンクリスト(単一リンクリスト)が与えられたとき、両方のリストに共通して存在するノードの総数を求める問題を考えてみましょう。例えば、2つのリストが [15, 16, 10, 9, 7, 17] と [15, 16, 40, 6, 9] の場合、共通する値は「15」「16」「9」の3つであるため、共通ノードの数は 3 となります。

アルゴリズムの考え方

最も基本的なアプローチは、ネストした2つのループを使って両方のリストを走査する方法です。具体的には以下の手順で処理を行います。

1. 最初のリストの各ノードについて、2番目のリスト内のいずれかのノードとデータが一致するかどうかを順番にチェックします。
2. 一致するノードが見つかった場合、カウンターを1つ増やし、2番目のリストの探索を打ち切って次のノードへ進みます(同じノードを二重にカウントしないため)。
3. すべてのノードに対して比較が完了したら、カウンターの値を結果として返します。

この手法では、リストの長さをそれぞれ n、m とすると、計算量は O(n × m) になります。シンプルで分かりやすい反面、大規模なリストには不向きなため、実用場面ではハッシュセットを併用して O(n + m) に高速化することも可能です。

サンプルコード(C++)

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
   Node *next;
};
// リストの先頭に新しいノードを挿入する関数
void prepend(Node** start, int new_data) {
   Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = NULL;
   if ((*start) != NULL){
      new_node->next = (*start);
      *start = new_node;
   }
   (*start) = new_node;
}
// 共通ノードの数を数える関数
int countCommonNodes(Node** start1, Node** start2) {
   Node* ptr = *start1;
   Node* ptr1 = *start2;
   int count = 0;
   while (ptr != NULL) {
      while (ptr1 != NULL) {
         if (ptr->data == ptr1->data) {
            count++;
            break;
         }
         ptr1 = ptr1->next;
      }
      ptr1 = *start2; // 2番目のリストのポインタを先頭に戻す
      ptr = ptr->next;
   }
   return count;
}
int main() {
   Node* first = NULL;
   Node* second = NULL;
   // 1つ目のリストを作成
   prepend(&first, 15);
   prepend(&first, 16);
   prepend(&first, 10);
   prepend(&first, 9);
   prepend(&first, 7);
   prepend(&first, 17);
   // 2つ目のリストを作成
   prepend(&second, 15);
   prepend(&second, 16);
   prepend(&second, 40);
   prepend(&second, 6);
   prepend(&second, 9);
   cout << "Number of common nodes:" << countCommonNodes(&first, &second);
}

実行結果

Number of common nodes:3

このプログラムでは、prepend() 関数によって各リストの先頭にノードを追加しながらリストを構築し、countCommonNodes() 関数で二重ループによる全件比較を行っています。その結果、2つのリストに共通するノード数として「3」が出力されます。