LeetCode Solutions
817. Linked List Components
Time: $O(n)$ Space: $O(|\texttt{G}|)$
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
int ans = 0;
unordered_set<int> setG{begin(G), end(G)};
for (; head; head = head->next)
if (setG.count(head->val) &&
(!head->next || !setG.count(head->next->val)))
++ans;
return ans;
}
};
class Solution {
public int numComponents(ListNode head, int[] G) {
int ans = 0;
Set<Integer> setG = new HashSet<>();
for (final int g : G)
setG.add(g);
for (; head != null; head = head.next)
if (setG.contains(head.val) && (head.next == null || !setG.contains(head.next.val)))
++ans;
return ans;
}
}
class Solution:
def numComponents(self, head: ListNode, G: List[int]) -> int:
ans = 0
G = set(G)
while head:
if head.val in G and (head.next == None or head.next.val not in G):
ans += 1
head = head.next
return ans