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