817 linked list components

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def (self, head, G):
"""
:type head: ListNode
:type G: List[int]
:rtype: int
"""
pointer = head
count = 0
conti = False
Gset = set(G)
while pointer != None:
if pointer.val in Gset:
conti = True
else:
if conti == True:
count+=1
conti = False
pointer = pointer.next
if conti == True:
count+=1
return count

Time Complexity: O(n)
Space Complexity: O(2)

create a set of G to reduce time complexity of get element form G
go through list, if there is element not in set, means there is a break
add 1 if the last x element is continuous