C++の3つのリンクリストで共通の要素を検索します

3つのリンクリストがあるとします。これらの3つのリンクリストに存在するすべての一般的な要素を見つける必要があります。これらのリストが[10、12、15、20、25]、[10、12、13、15]、および[10、12、15、24、25、26]であるとすると、これら3つのリストの共通要素は10です。 、12および15。

この問題を解決するためにハッシュ手法を使用します。これを解決するには、次の手順に従う必要があります-

• 空のハッシュテーブルを作成し、最初のテーブルの各要素を調べて要素を挿入し、頻度を1としてマークします

• 2番目のリンクリストを繰り返し、要素の現在の頻度が1の場合は、2にします。

• 3番目のリンクリストを繰り返し、要素の現在の頻度が2の場合は、3にします

• ここで、最初のリストをもう一度繰り返して要素の頻度を確認します。頻度が3の要素がある場合は、その要素を印刷して、次の要素に進みます

  。

例

#include<iostream>
#include<cmath>
#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;
}
void findCommonValues(Node* list1, Node* list2, Node* list3) {
   unordered_map<int, int> hash;
   Node* p = list1;
   while (p != NULL) {
      hash[p->data] = 1;
      p = p->next;
   }
   Node* q = list2;
   while (q != NULL) {
      if (hash.find(q->data) != hash.end()) hash[q->data] = 2;
         q = q->next;
   }
   Node* r = list3;
   while (r != NULL) {
      if (hash.find(r->data) != hash.end() && hash[r->data] == 2)
         hash[r->data] = 3;
      r = r->next;
   }
   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