Giả sử có hai danh sách liên kết đơn. Tìm tổng số nút chung của cả hai. Nếu hai danh sách [15, 16, 10, 9, 7, 17] và [15, 16, 40, 6, 9], có 3 nút chung.
Duyệt cả hai đến cuối bằng hai vòng lặp lồng, với mỗi nút danh sách 1, kiểm tra khớp nút nào của danh sách 2. Nếu khớp tăng bộ đếm, cuối cùng trả về đếm.
Ví dụ mã nguồn
#include<iostream> using namespace std; class Node { public: int data; Node *next; }; void prepend(Node** start, int new_data) { Node* new_node = new Node; new_node->data = new_data; new_node->next = NULL; if ((*start) != NULL){ new_node->next = (*start); *start = 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->next; } ptr1 = *start2; ptr = ptr->next; } return count; } int main() { Node* first = NULL; Node* second = NULL; prepend(&first, 15); prepend(&first, 16); prepend(&first, 10); prepend(&first, 9); prepend(&first, 7); prepend(&first, 17); prepend(&second, 15); prepend(&second, 16); prepend(&second, 40); prepend(&second, 6); prepend(&second, 9); cout << "Number of common nodes:" << countCommonNodes(&first, &second); } Kết quả
Number of common nodes:3