Các thành phần danh sách được liên kết trong C ++

Giả sử chúng ta đã đưa ra một cái đầu; đây là nút đầu của danh sách liên kết chứa các giá trị số nguyên duy nhất. Bây giờ chúng ta cũng được cung cấp danh sách G, một tập hợp con của các giá trị trong danh sách được liên kết. Chúng ta phải tìm số lượng các thành phần được kết nối trong G, nơi hai giá trị được kết nối nếu chúng xuất hiện liên tiếp trong danh sách được liên kết. Vì vậy, nếu danh sách giống như [0,1,2,3] và G =[0,1,3], thì đầu ra sẽ là 2, vì 0 và 1 được kết nối, vì vậy có hai danh sách [0,1] và [3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, tạo một tập hợp s và chèn tất cả các phần tử của G vào s
• cờ:=false
• while head không rỗng
  • x:=giá trị của head
  • nếu s có x, thì
    • nếu cờ sai, hãy tăng số lượt truy cập lên 1
    • cờ:=true
  • nếu không, hãy đặt cờ:=false
  • head:=tiếp theo của head
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
class Solution {
   public:
   int numComponents(ListNode* head, vector<int>& G) {
      int ret = 0;
      set < int > s;
      for(int i = 0; i < G.size(); i++)s.insert(G[i]);
      bool flag = false;
      while(head){
         int x = head->val;
         if(s.count(x)){
            if(!flag) ret++;
            flag = true;
         }else flag = false;
         head = head->next;
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {0,1,2,3};
   vector<int> v2 = {0,1,3};
   ListNode *h1 = make_list(v1);
   Solution ob;
   cout << (ob.numComponents(h1, v2));
}

Đầu vào

[0,1,2,3]
[0,1,3]

Đầu ra

2