title: LeetCode每日一题之817题链表组件
id: a1
date: 2022-10-12 14:12:47
tags: leetcode
cover: true
categories: leetcode
sidebar: true
- 链表组件 中等 给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。
返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
*
- 输入: 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 是两个组件，故返回 2。
public static int numComponents(ListNode head, int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
ListNode p = head;
int count =0;
while (p != null){
if(set.contains(p.val) && (p.next == null || !set.contains(p.next.val))) count ;
p = p.next;
}
return count;
}
public static void main(String[] args) {
ListNode head = new ListNode();
ListNode nextNode;
nextNode=head;
int[] nodes = {0,1,2};
for(int i=0;i<nodes.length;i ){
ListNode node = new ListNode(nodes[i]);
nextNode.next=node;
nextNode=nextNode.next;
}
int[] nums = {0,2};
int i = numComponents(head, nums);
System.out.println(i);
}示例
817
