C ++中的链接列表组件

假设我们给了个头；这是包含唯一整数值的链表的头节点。现在，我们还获得了列表G，它是链接列表中值的子集。我们必须找到G中已连接组件的数量，如果两个值连续出现在链表中，则两个值将被连接。因此，如果列表类似于[0,1,2,3]且G = [0,1,3]，则输出将为2，因为连接了0和1，所以有两个列表[0,1]和[3]。

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0，设置set，然后将G的所有元素插入s

• 标志：=假

• 而head不为null

• 如果标志为假，则将ret增加1

• 标志：= true

• x：=头值

• 如果s有x，则

• 否则设置标志：= false

• 头：=头的下一个

• 返回ret

让我们看下面的实现以更好地理解-

示例

#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));
}

输入值

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

输出结果

2