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:
n.1 <= n <= 1040 <= Node.val < nNode.val are unique.1 <= nums.length <= n0 <= nums[i] < nnums are unique.This approach leverages a set data structure to quickly determine if a node from the linked list is part of the 'nums' array. We traverse the linked list and use the set to track connected components. If a node is found in the set and it is not part of an ongoing component, we start a new component and continue the counter until we find a break in connectivity.
This C implementation uses an array as a simple hashset to mark elements present in 'nums'. We iterate through the linked list and check if each node value exists in the hashset. We maintain a boolean flag 'in_component' to track if we are currently traversing a connected component of 'nums'. Whenever we reach a node from 'nums' not preceded by another node in 'nums', we increment our component counter.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'.
Space Complexity: O(n) due to the hashset used for quick lookup.
This alternative approach first marks the initial position of all nodes existing in 'nums' by setting their value offsets to a special marker. In a second pass, it counts connected sequences between marked nodes. This enables direct marking of active components without extra space dedicated to hashes or sets but works best only when the linked list structure is such that in-place marking is feasible.
The C implementation performs list traversal to adjust node values based on component existence (conceptually), with a boolean counter tracking transitions into distinct components. As the standard C language lacks facilities for safe in-place data marking via addresses directly, memory strategy handled here targets traversal adjustments for ideal step-by-step reference marking. (Note: abstract — typically requires head management outside if values manipulate!)
Python
Time Complexity: O(n * m), as repeated search across elements within restricted logic.
Space Complexity: O(1), maintaining constant markers within node itself, with ideal suggesting!
| Approach | Complexity |
|---|---|
| Set for Quick Lookup | Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'. |
| Two-Pass on Linked List without Extra Space (Optimized for nums) | Time Complexity: O(n * m), as repeated search across elements within restricted logic. |
Number of Connected Components in an Undirected Graph - Union Find - Leetcode 323 - Python • NeetCode • 205,472 views views
Watch 9 more video solutions →Practice Linked List Components with our built-in code editor and test cases.
Practice on FleetCode