Reference: LeetCode
Difficulty: Medium

## Problem

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example:

Note:

• If N is the length of the linked list given by head, 1 <= N <= 10000.
• The value of each node in the linked list will be in the range [0, N - 1].
• 1 <= G.length <= 10000.
• G is a subset of all values in the linked list.

## Analysis

Methods:

1. Build Graph + DFS
• $U \rightarrow V$. Add edges (links in the list) between $U$ and $V$ if both $U$, $V$ are in $G$.
• Then use DFS to find all CCs (connected components).
• Time: $O(N)$
• Space: $O(N)$
2. Property of List
• As for 0->1->2->3->4 and G = [0, 3, 1, 4], set the list node $1$ if the node in $G$, or $0$ if not.
• The result is 1->1->0->1->1.
• Steps:
• Go over each node in head:
• If this node in G,
• count plus one.
• Check if successive nodes are in G.
• If encounter a node not in G then stop.
• Reach null, done.
• Go to the next node.
• If this node not in G, go to the next node.
• Time: $O(NG)$ and $O(N^2)$ in the worst case.
• $O(N)$: Go over each node in head if there are $N$ nodes in total.
• $O(G)$: Check if a node in G takes $G$ times upper bounded by $N$ since G is a subset.
• Space: $O(1)$
3. HashSet Improvement
• Convert the G array into a HashSet first.
• Do the same procedures above.
• Time: $O(N + G)$ is bounded by $O(N) = O(N + N)$
• Space: $O(G)$

Note: In terms of the implementation, there are two ways. It turns out that counting the number of 1->0 and 1->null is more intuitive.

## Code

### Property of List

Note:

• Notice the corner case.

### HashSet

Note:

• There is no better way to convert an array of primitive types to a set. Arrays.asList(array_primitive) will return a list of array.

Using 1->0 or 1->null:

Comment Junhao Wang
a software engineering cat