原文链接: https://leetcode-cn.com/problems/linked-list-components

英文原文

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 in nums 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.

中文题目

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。

同时给定列表 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 是链表中所有结点的值的一个子集.

通过代码

官方题解

线性扫描：

我们对链表进行一次扫描，一个组件在链表中对应一段极长的连续节点，因此如果当前的节点在列表 G 中，并且下一个节点不在列表 G 中，我们就找到了一个组件的尾节点，可以将答案加 1。

例如，当链表为 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，G 为 [0, 2, 3, 5, 7] 时，我们扫描之后可以发现 0, 3, 5, 7 四个节点是组件的尾节点，那么答案就为 4。

[sol1]
class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> Gset = new HashSet();
        for (int x: G) Gset.add(x);

        ListNode cur = head;
        int ans = 0;

        while (cur != null) {
            if (Gset.contains(cur.val) &&
                    (cur.next == null || !Gset.contains(cur.next.val)))
                ans++;
            cur = cur.next;
        }

        return ans;
    }
}

[sol1]
class Solution(object):
    def numComponents(self, head, G):
        Gset = set(G)
        cur = head
        ans = 0
        while cur:
            if (cur.val in Gset and
                    getattr(cur.next, 'val', None) not in Gset):
                ans += 1
            cur = cur.next

        return ans

复杂度分析

• 时间复杂度：$O(N + |G|)$，其中 N 是链表中的节点个数。

• 空间复杂度：$O(|G|)$，我们需要将 G 中的元素存储到无序集合中，用来快速判断一个节点是否出现在 G 中。

统计信息

通过次数	提交次数	AC比率
13947	23558	59.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言