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.Problem Overview: You are given the head of a linked list and an array nums containing a subset of node values. A component is a group of consecutive nodes in the list where every node value appears in nums. The task is to count how many such connected components exist.
Approach 1: Set for Quick Lookup (O(n) time, O(k) space)
The cleanest solution uses a hash table (set) to quickly check whether a node value exists in nums. Insert all values from nums into a set, then iterate through the linked list once. When the current node value exists in the set and the next node either does not exist in the set or is null, you found the end of a component. Increment the counter. The key insight: each component is counted exactly once at its boundary (the last node belonging to that component). Membership checks become O(1) due to hashing, so the full traversal remains linear. This approach is straightforward and performs well even when nums is large.
Approach 2: Two-Pass on Linked List without Extra Space (O(n * k) time, O(1) space)
If you want to avoid additional memory, skip the hash set and work directly with the array nums. Traverse the linked list and determine membership by scanning the nums array each time you need to check if a value belongs to the subset. Similar to the set approach, you detect a component when the current node value exists in nums and the next node either does not belong to nums or is null. Because each membership test scans the array, the complexity becomes O(n * k), where k is the size of nums. The benefit is constant extra space. This works when nums is small or memory usage is tightly constrained.
Recommended for interviews: The hash set approach is what most interviewers expect. It demonstrates that you recognize the repeated membership check and optimize it with constant-time lookups. Mentioning the no-extra-space variation shows awareness of trade-offs, but the O(n) hash set solution best balances clarity and efficiency.
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.
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!)
C (with assumption modifications)
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!
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set for Quick Lookup | O(n + k) | O(k) | General case. Fast membership checks using a hash set. |
| Two-Pass without Extra Space | O(n * k) | O(1) | Useful when memory is constrained or nums size is very small. |
817. Linked List Components | LEETCODE MEDIUM | LINKED LIST • code Explainer • 4,011 views views
Watch 9 more video solutions →Practice Linked List Components with our built-in code editor and test cases.
Practice on FleetCode