[LeetCode] 817. 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，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-components
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道链表题，我直接讲思路。因为 input 给的数组元素都是 unique 的，所以我用一个 hashset 记录所有出现过的元素。接着我再从链表的头结点开始遍历整个链表。对于当前节点 cur，如果他存在于 hashset，那么起码他就是某个链表组件的一部分，count 就要++。接着往后看，如果 cur 的下一个节点 cur.next 也存在于 hashset，那么说明 cur 和 cur.next 都是当前这个组件的一部分，count保持不变。如果中间有断开的情形，那么当我们再遇到另一个存在于 hashset 的节点的时候，就说明找到了一个新的链表组件。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public int numComponents(ListNode head, int[] nums) {
13         HashSet<Integer> set = new HashSet<>();
14         for (int num : nums) {
15             set.add(num);
16         }
17         
18         ListNode cur = head;
19         int count = 0;
20         while (cur != null) {
21             if (set.contains(cur.val)) {
22                 count++;
23                 while (cur != null && set.contains(cur.val)) {
24                     cur = cur.next;
25                 }
26             } else {
27                 cur = cur.next;
28             }
29         }
30         return count;
31     }
32 }

LeetCode 题目总结