Problem

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 innums where two values are connected if they appearconsecutively in the linked list.

Examples

Example 1

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2021/07/22/lc-linkedlistcom1.jpg)

    
    
    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

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2021/07/22/lc-linkedlistcom2.jpg)

    
    
    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 <= 10^4
  • 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.

Solution

Method 1 – Hash Set Traversal (1)

Intuition

We want to count contiguous segments in the linked list where all nodes’ values are in the given set nums. By using a hash set for quick lookup, we can traverse the list and count the start of each new component.

Approach

  1. Store all values from nums in a hash set for O(1) lookup.
  2. Traverse the linked list node by node.
  3. For each node, if its value is in the set and either it’s the start of the list or the next node is not in the set, increment the component count.
  4. Continue until the end of the list.
  5. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0;
        while (head) {
            if (s.count(head->val) && (!head->next || !s.count(head->next->val)))
                ans++;
            head = head->next;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numComponents(head *ListNode, nums []int) int {
    s := make(map[int]bool)
    for _, v := range nums {
        s[v] = true
    }
    ans := 0
    for head != nil {
        if s[head.Val] && (head.Next == nil || !s[head.Next.Val]) {
            ans++
        }
        head = head.Next
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int ans = 0;
        while (head != null) {
            if (set.contains(head.val) && (head.next == null || !set.contains(head.next.val)))
                ans++;
            head = head.next;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numComponents(head: ListNode?, nums: IntArray): Int {
        val set = nums.toHashSet()
        var ans = 0
        var node = head
        while (node != null) {
            if (set.contains(node.`val`) && (node.next == null || !set.contains(node.next.`val`)))
                ans++
            node = node.next
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: list[int]) -> int:
        s = set(nums)
        ans = 0
        while head:
            if head.val in s and (not head.next or head.next.val not in s):
                ans += 1
            head = head.next
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn num_components(head: Option<Box<ListNode>>, nums: Vec<i32>) -> i32 {
        use std::collections::HashSet;
        let s: HashSet<_> = nums.into_iter().collect();
        let mut ans = 0;
        let mut node = head.as_ref();
        while let Some(n) = node {
            if s.contains(&n.val) && (n.next.is_none() || !s.contains(&n.next.as_ref().unwrap().val)) {
                ans += 1;
            }
            node = n.next.as_ref();
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    numComponents(head: ListNode | null, nums: number[]): number {
        const s = new Set(nums);
        let ans = 0;
        let node = head;
        while (node) {
            if (s.has(node.val) && (!node.next || !s.has(node.next.val))) {
                ans++;
            }
            node = node.next;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Each node is visited once.
  • 🧺 Space complexity: O(m), where m is the length of nums, for the hash set.