Approach #1: Grouping [Accepted]
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.
Scanning through the list, if
node.val is in
node.next.val isn't (including if
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
Time Complexity: , where is the length of the linked list with root node
Space Complexity: , to store
Analysis written by: @awice.