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