链表组件00

题目链接

链表组件

题目描述

注意

• 链表中每个节点的值都是唯一的
• 数组是链表整型值的一个子集，也就是数组中的值都一定可以在链表中找到且数组的长度小于链表的长度

解答思路

• 根据题目意思，需要找到作为新开头的链表节点也就是组件的个数，所以需要定义这样一个变量isNew，如果当前节点无法在数组中找到，则下一个能在数组中找到的链表节点一定是作为新开头的链表节点，此时isNew为true；相对的，如果当前节点能够在数组中找到且此时isNew为true，则找到了一个新开头，且下一个链表节点如果也能在数组中找到，它们是连续的，此时isNew为false

代码

/**
 * 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) {
        int res = 0;
        boolean isNew = true;
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
            set.add(num);
        }
        while(head != null) {
            if(!set.contains(head.val)) {
                isNew = true;
            } else if(isNew) {
                res++;
                isNew = false;
            }
            head = head.next;
        }
        return res;
    }
}

关键点

• 相比于List，使用Set存储数组中的元素，查询速度更快能够节省更多时间
• 注意什么时候为新开头，什么时候组件是连续的