Linked List Components - Leetcode Solution

Problem Description:

We are given a linked list and an array of integers called G.

We define a connected component as follows - any two adjacent elements in the linked list are a part of the same component if and only if their values appear in G.

Subtask: Return the number of connected components in G.

Solution Approach:

The given problem can be solved using following steps:

Step 1 - Create a hashSet and add all the values of array G in it to make the lookup of values faster while traversing the Linked List.

Step 2 - Traverse the Linked List and check if the current node's value is present in the hashSet. A component starts from the first node whose values match in G, and it continues till we reach a node whose value is not present in G.

Step 3 - Keep a track of the number of components we have encountered so far.

Step 4 - Finally, return the count of connected components.

Time Complexity Analysis:

In the above approach, we are iterating through the entire Linked List and comparing each node's value with all the elements present in array G. This adds up to linear time complexity of O(n * G.length), where n is the length of the Linked List and G.length is the length of the array G.

Code Implementation:

Here is the code implementation of the above-described approach -

class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> set = new HashSet<>();
        for (int num : G) set.add(num);
        ListNode node = head;
        int count = 0, flag = 0;
        while (node != null) {
            if (set.contains(node.val)) {
                flag = 1;
            } else if (flag == 1) {
                count++;
                flag = 0;
            }
            node = node.next;
        }
        if (flag == 1) count++;
        return count;
    }
}

The above code has been executed successfully on the LeetCode platform, and it passes all the test cases.

1