Linked List Components in Java

Given the head of a singly linked list and an integer array G representing a subset of node values. The task is to determine the number of connected components in the linked list that contain only values from G.

Example 1

Input:

Linked List: 0 -> 1 -> 2 -> 3

Subset G = {0, 1, 3}

Output: 2

Explanation: The components {0, 1} and {3} are separate, as 2 is not in G, breaking the continuity.

Example 2

Input:

Linked List: 0 -> 1 -> 2 -> 3 -> 4

Subset G = {0, 3, 1, 4}

Output: 2

Explanation: The components {0, 1} and {3, 4} are separate because 2 is not in G, breaking the continuity.

Example 3

Input:

Linked List: 1 -> 2 -> 3 -> 4 -> 5

Subset G = {2, 3, 4}

Output: 1

Explanation: Nodes {2, 3, 4} are consecutive in the list, forming one connected component.

Approach 1: Using HashSet Approach

The HashSet approach to check whether a node's value belongs to the given subset G.

Algorithm

Step 1: Store all values of G in a HashSet.

Step 2: Traverse the linked list and check if the current node's value exists in the HashSet.

Step 3: If the current node is in G and its next node is not in G (or is null), increment the count since it marks the end of a connected component.

Step 4: Move to the next node and continue the process.

Step 5: Return the total number of connected components.

Output:

 2 

Time Complexity: The time complexity of a program is O(n). This is because we traverse the linked list once.

Space Complexity: The space complexity of a program is O(k). This is because the HashSet stores up to k elements from G.

Approach 2: Sorting and Binary Search Approach

The binary search on a sorted array G to efficiently determine if a node's value is part of the subset. We traverse the linked list and count the number of connected components by checking contiguous nodes in G.

Algorithm

Step 1: Sort the array G to enable fast lookups using binary search.

Step 2: Initialize a count variable to keep track of the number of components.

Step 3: Traverse the linked list:

Step 3.1: Use binary search (Arrays.binarySearch()) to check if the current node is in G.

Step 3.2: If a new component starts (node is in G but the previous was not), increment the count.

Step 3.3: If the node is not in G, mark the end of a component.

Step 4: Return the final count of connected components.

Output:

 2 

Time Complexity: The time complexity of a program is O(n log k). This is because sorting takes O(k log k), traverses the linked list takes O(n) and binary search takes O(log k).

Space Complexity: The space complexity of a program is O(1). This is because no extra space is used apart from input storage.