leetcode 817 链表组件

问题描述 :
给定链表头结点 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
#include
#include 
using namespace std;

using std::vector;
using std::count;
using std::cout;
using std::endl;

struct ListNode
{
    int val;
    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& G) {
             //填充本函数完成功能
        ListNode *p1=head;
        int num=0;
        int flag=1;//设置目的，是否可以作为一个新组件
        while(p1!=NULL)
        {
             if (count(G.begin(), G.end(), p1->val)) //搜索G中是否有和p1->val一样的值
             {
                 if(flag==1)
                    num++;//一致时，若可以作为一个新组建，num++
                 if(p1->next!=NULL&&count(G.begin(), G.end(), p1->next->val)) //当p1的下一个元素的val值在G中也存在，这时就不能作为一个新组件
                 {
                     flag=0;//所以flag=0
                 }
                 else flag=1;
             }
             p1=p1->next;//判断完了当前结点p1，指针后移
        }
        return num;
    }
};
ListNode *createByTail()
{
    ListNode *head;
    ListNode *p1,*p2;
    int n=0,num;
    int len;
    cin>>len;
    head=NULL;
    while(n>num)
    {
        p1=new ListNode(num);
        n=n+1;
        if(n==1)
            head=p1;
        else
            p2->next=p1;
        p2=p1;
    }
    return head;
}
int main()
{
    vector G;
    int m,data,res;
    ListNode* head = createByTail();
    cin>>m;
    for(int i=0; i
        cin>>data;
        G.push_back(data);
    }
    res=Solution().numComponents(head,G);
    cout< 
补充知识点
 
C++中count函数用法：
 count函数可以用来统计字符串中某个字符的个数
 使用方法是：
 count（begin，end，‘a’）
 其中begin指的是起始地址
 end指的是结束地址
 第三个参数指的是需要查找的字符。