Cho hai danh sách liên kết đôi, đếm số nút chung. Ví dụ [15,16,10,9,7,17] và [15,16,40,6,9] → 3 nút chung.
Duyệt cả hai danh sách bằng hai lồng nhau, so sánh từng nút, nếu khớp tăng 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); }
Kết quả
Number of common nodes:3