817. 链表组件 : 简单链表模拟题

题目描述

这是 LeetCode 上的 ​​817. 链表组件​​ ，难度为 中等。

Tag : 「链表」、「模拟」、「哈希表」

给定链表头结点 ​

​head​

​​，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 ​

​nums​

​，该列表是上述链表中整型值的一个子集。

返回列表 ​

​nums​

​​ 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 ​

​nums​

​ 中）构成的集合。

示例 1：

输入: head = [0,1,2,3], nums = [0,1,3]

输出: 2

解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3]      

示例 2：

输入: head = [0,1,2,3,4], nums = [0,3,1,4]

输出: 2

解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4]      

提示：

• 链表中节点数为​

  ​n​

  ​
• ​

  ​Node.val​

  ​ 中所有值 不同
• ​

  ​nums​

  ​ 中所有值 不同

模拟

根据题意进行模拟即可 : 为了方便判断某个 是否存在于 ​​

​nums​

​​ 中，我们先使用 ​

​Set​

​​ 结构对所有的

Java 代码：

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        while (head != null) {
            if (set.contains(head.val)) {
                while (head != null && set.contains(head.val)) head = head.next;
                ans++;
            } else {
                head = head.next;
            }
        }
        return      

TypeScript 代码：

function numComponents(head: ListNode | null, nums: number[]): number {
    let ans = 0
    const set = new Set<number>()
    for (const x of nums) set.add(x)
    while (head != null) {
        if (set.has(head.val)) {
            while (head != null && set.has(head.val)) head = head.next
            ans++
        } else {
            head = head.next
        }
    }
    return      

Python 代码：

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        ans = 0
        nset = set([x for x in nums])
        while head:
            if head.val in nset:
                while head and head.val in nset:
                    head = head.next
                ans += 1
            else:
                head = head.next
        return      

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 ​

​No.817​

​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。