Giả sử chúng ta có ba danh sách được liên kết. Chúng ta phải tìm tất cả các yếu tố chung có trong ba danh sách liên kết này. Giả sử các danh sách này là [10, 12, 15, 20, 25], [10, 12, 13, 15] và [10, 12, 15, 24, 25, 26], thì phần tử chung trong ba danh sách này là 10 , 12 và 15.
Chúng tôi sẽ sử dụng kỹ thuật băm để giải quyết vấn đề này. Để giải quyết vấn đề này, chúng ta phải làm theo các bước sau -
-
Tạo một bảng băm trống và xem qua từng phần tử trong bảng đầu tiên, chèn các phần tử và đánh dấu tần suất là 1
-
Lặp lại qua danh sách được liên kết thứ hai, sau đó nếu tần suất hiện tại là 1 cho phần tử, thì hãy đặt nó thành 2
-
Lặp lại qua danh sách được liên kết thứ ba, sau đó nếu tần suất hiện tại là 2 cho phần tử, thì hãy đặt nó thành 3
-
Bây giờ, hãy lặp lại danh sách đầu tiên một lần nữa để kiểm tra tần suất của các phần tử, nếu có một phần tử nào đó có tần số là 3, thì hãy in phần tử đó và chuyển sang bước tiếp theo
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);
} Đầu ra
Common elements are: 10 12 15