问题描述 :
给定链表头结点 head，该链表上的每个结点都有一个唯一的整型值 。
同时给定列表 G，该列表是上述链表中整型值的一个子集。
返回列表 G 中组件的个数，这里对组件的定义为：链表中一段极长连续结点的值（该值必须在列表 G 中）构成的集合。极长的含义是：这段连续结点的前面或后面结点不属于G。
示例 1：
输入: head: 0->1->2->3 G = [0, 1, 3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入: head: 0->1->2->3->4 G = [0, 3, 1, 4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
说明：
如果 N 是给定链表 head 的长度，1 <= N <= 10000。
链表中每个结点的值所在范围为 [0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集.
输入说明 :
首先输入链表长度len，然后输入len个整数，以空格分隔。
再输入G的大小m，然后输入m个整数，以空格分隔。
输出说明 :
输出一个整数，表示结果。
输入范例： 4 0 1 2 3 3 0 1 3
输出范例： 2
#include<iostream> #include<vector> using namespace std; struct ListNode{ int val; struct ListNode *next; ListNode() : val(0), next(NULL) {} ListNode(int x) : val(x), next(NULL) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: int numComponents(ListNode* head, vector<int>& G) { //填充本函数完成功能 int a[10000]; int num=0,flag=0; ListNode *p=head->next; for(int i=0;i<10000;i++) a[i]=-1; for(int j=0;j<G.size();j++) a[G[j]]=G[j]; while(p){ if(a[p->val]!=-1){ flag=1; if(p->next==NULL) num++; } else{ if(flag==1){ flag=0; num++; } } p=p->next; } return num; } }; ListNode *createByTail() { ListNode *head; ListNode *p1,*p2; int n=0,num; int len; cin>>len; head=NULL; while(n<len && cin>>num) { p1=new ListNode(num); n=n+1; if(n==1) head=p1; else p2->next=p1; p2=p1; } return head; } int main() { vector<int> G; int m,data,res; ListNode* head = createByTail(); cin>>m; for(int i=0;i<m;i++){ cin>>data; G.push_back(data); } res=Solution().numComponents(head,G); cout<<res<<endl; return 0; }