LeetCode 817: Linked List Components

Explanation

To solve this problem, we can iterate through the linked list and the given array nums at the same time. We can use a set to store the values in nums for faster lookup. While iterating through the linked list, we check if the current value and the next value are both in the set. If they are, we increment a counter for connected components. After iterating through the linked list, we return the total count of connected components.

• Time complexity: O(n) where n is the number of nodes in the linked list
• Space complexity: O(m) where m is the number of elements in the nums array

public int numComponents(ListNode head, int[] nums) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);
    }

    int count = 0;
    while (head != null) {
        if (numSet.contains(head.val) && (head.next == null || !numSet.contains(head.next.val))) {
            count++;
        }
        head = head.next;
    }

    return count;
}