Approach #1: Grouping [Accepted]
Intuition
Instead of thinking about connected components in G
, think about them in the linked list. Connected components in G
must occur consecutively in the linked list.
Algorithm
Scanning through the list, if node.val
is in G
and node.next.val
isn't (including if node.next
is null
), then this must be the end of a connected component.
For example, if the list is 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7
, and G = [0, 2, 3, 5, 7]
, then when scanning through the list, we fulfill the above condition at 0, 3, 5, 7
, for a total answer of 4
.
Complexity Analysis

Time Complexity: , where is the length of the linked list with root node
head
. 
Space Complexity: , to store
Gset
.
Analysis written by: @awice.