Linked List Components
Problem
Given the head of a linked list with unique values and a list nums (a subset of the values), return the number of connected components in nums where two values are connected iff they are adjacent in the list.
head = [0,1,2,3], nums = [0,1,3]2def numComponents(head, nums):
s = set(nums)
cnt = 0
cur = head
while cur:
if cur.val in s and (cur.next is None or cur.next.val not in s):
cnt += 1
cur = cur.next
return cntvar numComponents = function(head, nums) {
const s = new Set(nums);
let cnt = 0, cur = head;
while (cur) {
if (s.has(cur.val) && (cur.next === null || !s.has(cur.next.val))) cnt++;
cur = cur.next;
}
return cnt;
};class Solution {
public int numComponents(ListNode head, int[] nums) {
java.util.Set<Integer> s = new java.util.HashSet<>();
for (int x : nums) s.add(x);
int cnt = 0;
ListNode cur = head;
while (cur != null) {
if (s.contains(cur.val) && (cur.next == null || !s.contains(cur.next.val))) cnt++;
cur = cur.next;
}
return cnt;
}
}class Solution {
public:
int numComponents(ListNode* head, vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int cnt = 0;
ListNode* cur = head;
while (cur) {
if (s.count(cur->val) && (cur->next == nullptr || !s.count(cur->next->val))) cnt++;
cur = cur->next;
}
return cnt;
}
};Explanation
A "component" here is a run of consecutive list nodes whose values all appear in nums. We want to count how many such runs there are. The slick way to count runs is to count their endings instead of trying to track when each one starts.
First we dump nums into a hash set s so we can check "is this value in nums?" instantly. Then we walk the list once with cur.
A node marks the end of a component when it is itself in the set AND its next node is either None or not in the set. That is exactly the condition cur.val in s and (cur.next is None or cur.next.val not in s). Each time it holds, we have just finished one run, so we do cnt += 1.
Since every component has exactly one ending node, counting endings gives the number of components directly.
Example: list 0 → 1 → 2 → 3 with nums = [0, 1, 3]. Node 1 is in-set and its next 2 is not, so that ends a component. Node 3 is in-set and is the last node, ending another. Total = 2.