C++의 세 연결 목록에서 공통 요소 찾기

연결된 목록이 세 개 있다고 가정합니다. 우리는 이 세 연결 목록에 있는 모든 공통 요소를 찾아야 합니다. 이 목록이 [10, 12, 15, 20, 25], [10, 12, 13, 15] 및 [10, 12, 15, 24, 25, 26]이라고 가정하고 이 세 목록의 공통 요소는 10입니다. , 12 및 15.

우리는 이 문제를 해결하기 위해 해싱 기술을 사용할 것입니다. 이 문제를 해결하려면 다음 단계를 따라야 합니다.

• 빈 해시 테이블을 생성하고 첫 번째 테이블의 각 요소를 살펴보고 요소를 삽입하고 빈도를 1로 표시

• 두 번째 연결 목록을 반복한 다음 현재 빈도가 요소에 대해 1이면 2로 만듭니다.

• 세 번째 연결 목록을 반복한 다음 요소의 현재 빈도가 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