Cho ba danh sách liên kết, tìm phần tử chung. Ví dụ [10,12,15,20,25], [10,12,13,15], [10,12,15,24,25,26] → 10, 12, 15.
Dùng hashing: tạo bảng băm, duyệt danh sách 1 gán tần suất 1; danh sách 2 nếu tần suất 1 thì thành 2; danh sách 3 nếu tần suất 2 thì thành 3; cuối cùng in các phần tử tần suất 3.
Ví dụ
#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); }
Kết quả
Common elements are: 10 12 15