Tìm các nút chung trong hai danh sách được liên kết đơn lẻ trong C ++

Giả sử chúng ta có hai danh sách được liên kết đơn lẻ. Chúng ta phải tìm tổng số nút chung trong cả danh sách được liên kết đơn lẻ. 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 *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);
}

Đầu ra

Number of common nodes:3