Coding Interview PatternsLinked List Components
MediumFast and Slow Pointers
Linked List Components
Explanation & Solution
Description
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.
Input:head = [0,1,2,3], nums = [0,1,3]
0
0
1
1
2
2
3
3
0
0
1
1
2
3
Output: 2
Explanation: The connected components are [0,1] and [3]. Node 2 is not in nums, so it breaks the chain.
Constraints
- The number of nodes in the list is in the range
[1, 10⁴] 0 <= Node.val < nwherenis the number of nodes- All values in the linked list are unique
numsis a subset of values in the linked list
Approach
Fast and Slow Pointers pattern
1. Build a Lookup Set
- Convert
numsinto aSetfor O(1) lookups. - This lets us quickly check if a node's value belongs to the target subset.
2. Traverse the Linked List
- Walk through each node using a
currpointer starting athead. - Maintain a boolean
inComponentto track whether we are currently inside a connected component. - Maintain a
countto track the number of components found.
3. Detect Component Boundaries
- If
curr.valis in the set and we are not already inside a component, incrementcountand setinComponent = true. - If
curr.valis not in the set, setinComponent = false— the current component (if any) has ended.
4. Return the Count
- After traversing the entire list,
countholds the number of connected components.
Key Insight
- A connected component starts whenever we transition from a node not in the set (or the start of the list) to a node in the set.
- We only need to count these transitions, not track the actual groups.
Time
O(n)single pass through the list plus O(n) to build the set.Space
O(m)where m is the size of `nums` for the hash set.Visualization
Input:
Linked List Traversal
—
No animation available
Slow (S)Fast (F)Both
0 steps