[LeetCode] 817. Linked List Components

[grandyang]

 

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.

Return  the number of connected components innums where two values are connected if they appear consecutively in the linked list.

 

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

 

Constraints:

• The number of nodes in the linked list is n.
• 1 <= n <= 104
• 0 <= Node.val < n
• All the values Node.val are unique.
• 1 <= nums.length <= n
• 0 <= nums[i] <= n
• All the values of nums are unique.

 

这道题给了我们一个链表，又给了一个结点值数组，里面不一定包括了链表中所有的结点值。让返回结点值数组中有多少个相连的组件，因为缺失的结点值会将原链表断开，实际上就是让求有多少个相连的子链表，题目中给的例子很好的说明题意。这道题并不需要什么特别高深的技巧，难懂的算法，直接按题目的要求来找就可以了。首先，为了快速的在结点值数组中查找某个结点值是否存在，可以将所有的结点值放到一个 HashSet 中，这样就能在常数级的时间复杂度中查找。然后就可以来遍历链表了，对于遍历到的每个结点值，只有两种情况，在或者不在 HashSet 中。不在 HashSet 中的情况比较好办，说明此时断开了，而在 HashSet 中的结点，有可能是该连续子链表的起始点，或者是中间的某个点，而计数器对该子链表只能自增1，所以需要想办法来 handle 这种情况。博主最先想到的办法是先处理不在 HashSet 中的结点，处理方法就是直接跳到下一个结点。那么对于在 HashSet 中的结点，首先将计数器 res 自增1，然后再来个循环，将之后所有在集合中的结点都遍历完，这样才不会对同一个子链表多次增加计数器，参见代码如下：

 

解法一：

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int res = 0;
        unordered_set<int> nodeSet(nums.begin(), nums.end());
        while (head) {
            if (!nodeSet.count(head->val)) {
                head = head->next;
                continue;
            }
            ++res;
            while (head && nodeSet.count(head->val)) {
                head = head->next;
            }
        }
        return res;
    }
};

 

我们可以稍稍修改代码，使其更加简洁，在遍历的时候进行判断，如果当前结点在集合中，并且当前结点是尾结点或者下一个结点不在集合中的时候，让计数器自增1，通过这种操作，不会多加也不会漏加计数器，参见代码如下：

 

解法二：

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int res = 0;
        unordered_set<int> nodeSet(nums.begin(), nums.end());
        while (head) {
            if (nodeSet.count(head->val) && (!head->next || !nodeSet.count(head->next->val))) {
                ++res;
            }
            head = head->next;
        }
        return res;
    }
};

 

Github 同步地址：

#817

 

参考资料：

https://leetcode.com/problems/linked-list-components/description/

https://leetcode.com/problems/linked-list-components/solution/

https://leetcode.com/problems/linked-list-components/discuss/123842/C++JavaPython-Easy-and-Concise-Solution-with-Explanation

 

LeetCode All in One 题目讲解汇总(持续更新中...)