Problem statement

https://leetcode.com/problems/linked-list-components/

Solution

Let us create set of nodes G and then what we need to find in fact number of nodes, such that this node is in set and next node not in set. We also need to create dummy variable before head.

Complexity

Time complexity is O(n), where n is length of linked list, space complexity is O(m) < O(n), where m is number of element in G.

Code

class Solution:
    def numComponents(self, head, G):
        set_G, ans, dummy = set(G), 0, ListNode(-1)
        dummy.next = head
        while dummy.next:
            if dummy.val not in set_G and dummy.next.val in set_G:
                ans += 1
            dummy = dummy.next
        return ans