You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.
Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.
Example 1:
Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.
Example 2:
Input: head = [0,1,2,3,4], nums = [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.
Constraints:
The number of nodes in the linked list is n.
1 <= n <= 104
0 <= Node.val < n
All the values Node.val are unique.
1 <= nums.length <= n
0 <= nums[i] < n
All the values of nums are unique.
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defnumComponents(self,head:Optional[ListNode],nums:List[int])->int:ans=0s=set(nums)whilehead:whileheadandhead.valnotins:head=head.nextans+=headisnotNonewhileheadandhead.valins:head=head.nextreturnans
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcnumComponents(head*ListNode,nums[]int)int{s:=map[int]bool{}for_,v:=rangenums{s[v]=true}ans:=0forhead!=nil{forhead!=nil&&!s[head.Val]{head=head.Next}ifhead!=nil{ans++}forhead!=nil&&s[head.Val]{head=head.Next}}returnans}