Giả sử chúng ta có hai danh sách được liên kết kép. Chúng ta phải tìm tổng số nút chung trong cả danh sách liên kết kép. Vì vậy, nếu hai danh sách giống như [15, 16, 10, 9, 7, 17] và [15, 16, 40, 6, 9], có ba nút chung.
Duyệt qua cả hai danh sách cho đến cuối danh sách bằng cách sử dụng hai vòng lặp lồng nhau, đối với mọi nút trong danh sách, hãy kiểm tra xem nó có khớp với bất kỳ nút nào của danh sách thứ hai hay không. Nếu tìm thấy kết quả phù hợp, hãy tăng bộ đếm và cuối cùng trả lại bộ đếm.
Ví dụ
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *back, *front;
};
void append(Node** start, int new_data) {
Node* new_node = new Node;
new_node->data = new_data;
new_node->back = NULL;
new_node->front = (*start);
if ((*start) != NULL)
(*start)->back = 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->front;
}
ptr1 = *start2;
ptr = ptr->front;
}
return count;
}
int main() {
Node* first = NULL;
Node* second = NULL;
append(&first, 15);
append(&first, 16);
append(&first, 10);
append(&first, 9);
append(&first, 7);
append(&first, 17);
append(&second, 15);
append(&second, 16);
append(&second, 40);
append(&second, 6);
append(&second, 9);
cout << "Number of common nodes:" << countCommonNodes(&first, &second);
} Đầu ra
Number of common nodes:3