# 817. Linked List Components

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:**

1 | head: 0->1->2->3 |

1 | head: 0->1->2->3->4 |

**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:**

- 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)$

- 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.

- Reach

- If encounter a node not in

- If this node not in
`G`

, go to the next node.

- Go over each node in
**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.

- $O(N)$: Go over each node in
**Space:**$O(1)$

- As for
- 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)$

- Convert the

**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

### Build Graph + DFS

1 | public int numComponents(ListNode head, int[] G) { |

### Property of List

**Note:**

- Notice the corner case.

1 | public int numComponents(ListNode head, int[] G) { |

### 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.

1 | public int numComponents(ListNode head, int[] G) { |

**Using 1->0 or 1->null:**

1 | public int numComponents(ListNode head, int[] G) { |

Comment