leetcode 817. 链表组件(java)

题目描述

给定链表头结点 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 中所有值 不同

HashSet 模拟

根据题意进行模拟即可 : 为了方便判断某个node.val 是否存在于 nums 中，我们先使用 Set 结构对所有的 nums[i] 进行转存，随后每次检查连续段（组件）的个数。

代码演示：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int numComponents(ListNode head, int[] nums) {Set<Integer>set = new HashSet<>();int count = 0;//方便进行判断，如果用数组判断，那么每次都要循环，这个优化很重要。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;}count++;}else{head = head.next;}}return count;}
}