Formatted question description: https://leetcode.ca/all/817.html

# 817. Linked List Components (Medium)

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:

Input:
G = [0, 1, 3]
Output: 2
Explanation:
0 and 1 are connected, so [0, 1] and  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 head1 <= 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.

Companies:

Related Topics:

## Solution 1.

// OJ: https://leetcode.com/problems/linked-list-components/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
unordered_set<int> s(G.begin(), G.end());
int ans = 0;
while (true) {
++ans;
}
return ans;
}
};


Java

• /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] G) {
Set<Integer> subset = new HashSet<Integer>();
for (int value : G)
boolean inComponent = false;
int components = 0;
while (node != null) {
int value = node.val;
if (subset.contains(value)) {
if (!inComponent) {
inComponent = true;
components++;
}
} else {
if (inComponent)
inComponent = false;
}
node = node.next;
}
return components;
}
}

• // OJ: https://leetcode.com/problems/linked-list-components/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
unordered_set<int> s(G.begin(), G.end());
int ans = 0;
while (true) {
++ans;
}
return ans;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
"""
:type G: List[int]
:rtype: int
"""
groups = 0
subset = set(G)