Linked List Components

IF
AlgoAxiomStaff Engineers
JSTS
Medium20 mins

Given the head of a linked list containing unique integer values and an array nums that is a subset of the linked list values, return the number of connected components formed by the values in nums.

A connected component is a maximal sequence of consecutive nodes in the linked list whose values all appear in nums.

Examples

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]

Output: 2

Explanation: The connected components are [0,1] and [3]. Node 2 is not in nums, so it breaks the chain.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]

Output: 2

Explanation: The connected components are [0,1] and [3,4]. Node 2 is not in nums, so it separates them.

Example 3:

Input: head = [0,1,2], nums = [0,1,2]

Output: 1

Explanation: All nodes are in nums, so the entire list is one connected component.

Constraints

  • The number of nodes in the list is in the range [1, 10⁴]
  • 0 <= Node.val < n where n is the number of nodes
  • All values in the linked list are unique
  • nums is a subset of values in the linked list
Source: Fast and Slow Pointers pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle