## 题目 #

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:

``````
Input:
G = [0, 1, 3]
Output: 2
Explanation:
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

``````

Example 2:

``````
Input:
G = [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.

``````

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.

## 代码 #

``````
package leetcode

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

func numComponents(head *ListNode, G []int) int {
return 1
}
gMap := toMap(G)
count := 0

for cur != nil {
if _, ok := gMap[cur.Val]; ok {
if cur.Next == nil { // 末尾存在，直接加一
count++
} else {
if _, ok = gMap[cur.Next.Val]; !ok {
count++
}
}
}
cur = cur.Next
}
return count
}

func toMap(G []int) map[int]int {
GMap := make(map[int]int, 0)
for _, value := range G {
GMap[value] = 0
}
return GMap
}

``````

Apr 8, 2023