817. Linked List Components

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };分析：长度为N的链表 每个节点的val都不一样 取值从0-N-1 空间复杂度为O(G,size()) 时间复杂度为O(m+n) */
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        if(!head) return 0;
        unordered_map<int,int> table;
        for(int each : G)
            ++table[each];
        ListNode* cur = head->next,* pre = head;
        int res = table[head->val]?1:0;
        while(cur) {
            if(table[cur->val]&&table[pre->val]==0)
                ++res;
            pre = cur;
            cur = cur->next;
        }
        return res;
    }
};

• 首先需要将G数组当中的元素信息存储在map当中，后续就不用再遍历

• 其次就是遍历链表的每个节点 如果其pre节点的值没有出现过说明当前节点是一个新子链表的头结点，计数加一，其他情况不用加。