题目形容
这是 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。示例 2：
输出: head = [0,1,2,3,4], nums = [0,3,1,4]输入: 2解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。提醒：
- 链表中节点数为
n - $1 <= n <= 10^4$
- $0 <= Node.val < n$
Node.val中所有值 不同- $1 <= nums.length <= n$
- $0 <= nums[i] < n$
nums中所有值 不同
模仿
依据题意进行模仿即可 : 为了不便判断某个 $node.val$ 是否存在于 nums 中，咱们先应用 Set 构造对所有的 $nums[i]$ 进行转存，随后每次查看间断段（组件）的个数。
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 ans; }}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 ans}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 ans- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.817 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布