Leetcode 96 链表组件

1 题目

817. 链表组件

给定链表头结点head，该链表上的每个结点都有一个唯一的整型值。同时给定列表nums，该列表是上述链表中整型值的一个子集。

返回列表nums中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表nums中）构成的集合。

示例 1：

输入:head = [0,1,2,3], nums = [0,1,3]输出:2解释:链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入:head = [0,1,2,3,4], nums = [0,3,1,4]输出:2解释:链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

提示：

• 链表中节点数为n
• 1 <= n <= 104
• 0 <= Node.val < n
• Node.val中所有值不同
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• nums中所有值不同

2 代码实现

思考

其实没什么思路，确认在不在这个num里面是不是构造unordered_map?

遍历，遇到不在map里的就停下来。然后对于“组件”写好count计数。

题解

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int numComponents(ListNode* head, vector<int>& nums) { unordered_set <int> num_set (nums.begin(), nums.end()); int count = 0 ; bool is_component =false; ListNode*cur = head ; while(cur !=nullptr){ if(num_set.count(cur ->val)){ if(!is_component){ count++; is_component = true; } }else{ is_component = false; } cur = cur -> next ; } return count; } };

具体分析你的思路

你提到的两个核心点：

1. 用哈希结构（unordered_map/unordered_set）判断值是否在 nums 中：这是解决这个问题的关键优化，因为如果直接遍历 nums 数组判断 “值是否存在”，时间复杂度会是 O (n*m)（n 是链表长度，m 是 nums 长度），而用哈希结构能把查询时间降到 O (1)，整体时间复杂度优化为 O (n+m)，这也是这道题的最优解法思路。

2. 小补充：你说的unordered_map也能用，但unordered_set更贴合需求（只需存值，无需键值对），空间和操作上更轻量，不过两者核心效果一致。

3. 遍历链表，遇到不在哈希结构里的就停下，统计组件 count：这个 “遇到不在就停下” 的思路，本质就是区分 “组件内” 和 “组件外” 的状态，和我代码里in_component标记的逻辑完全等价 —— 你的思路已经抓住了 “组件是最长连续段” 这个核心定义。

解题思路

1. 哈希集合优化查询：将 nums 数组存入unordered_set，使 “判断节点值是否在 nums 中” 的操作时间复杂度降为 O (1)（比 unordered_map 更轻量，因为只需存值无需存键值对）。
2. 遍历链表统计组件：
   • 初始化组件计数count为 0，标记in_component（表示当前是否处于一个组件中）为 false。
   • 遍历链表每个节点：
     • 如果节点值在集合中，且in_component为 false，说明进入了新组件，count+1并将in_component置为 true；
     • 如果节点值不在集合中，说明组件中断，将in_component置为 false。

C++ 核心代码（LeetCode 可直接提交）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int numComponents(ListNode* head, vector<int>& nums) { // 1. 将nums存入无序集合，快速查询 unordered_set<int> num_set(nums.begin(), nums.end()); int count = 0; // 组件个数 bool in_component = false; // 标记当前是否在组件中 // 2. 遍历链表 ListNode* curr = head; while (curr != nullptr) { if (num_set.count(curr->val)) { // 当前节点值在nums中，且未处于组件中 → 新组件开始 if (!in_component) { count++; in_component = true; } } else { // 当前节点值不在nums中 → 组件中断 in_component = false; } curr = curr->next; // 移动到下一个节点 } return count; } };

代码关键部分解释

1. 哈希集合初始化：unordered_set<int> num_set(nums.begin(), nums.end())直接将 nums 数组转为集合，利用集合的 O (1) 查询特性，避免遍历 nums 数组的 O (n) 查询。
2. 核心遍历逻辑：
   • num_set.count(curr->val)：判断当前节点值是否在 nums 中（count 返回 1 表示存在，0 表示不存在）。
   • in_component标记：避免重复计数同一组件（比如连续的 0、1 只会在 0 时计数一次）。
   • 只有 “从非组件状态进入组件状态” 时，才对count加 1，符合 “最长连续节点段” 的组件定义。

自己梳理以后再写的代码（有错）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int numComponents(ListNode* head, vector<int>& nums) { unordered_set <int> num_set (nums.begin(), nums.end()); int count = 0 ; bool is_component = true; ListNode*cur = head ; while(cur !=nullptr){ if(num_set.count(cur ->val)){ if(!is_component){ count++; is_component = true; }else{ is_component = false; } } cur = cur -> next ; } return count; } };

1.核心逻辑错误：状态翻转逻辑写反 + 缺失组件中断处理

• 错误表现：当节点值在nums中时，你错误地在else分支将is_component置为false（相当于 “进入组件后立刻标记为离开”），同时完全缺失 “节点值不在 nums 中时标记组件中断” 的else分支；
• 影响：这会导致组件的状态标记完全混乱，无法正确识别 “连续的组件段”，计数结果完全偏离预期。

2. 细节错误：状态初始值设置错误

• 错误表现：将is_component初始值设为true（默认 “处于组件中”）；
• 影响：遍历开始前本无任何节点，默认状态应为 “不在组件中（false）”，初始值错误会导致第一个属于组件的节点无法触发计数（比如示例 1 中第一个节点 0 本该让 count+1，却因!is_component为 false 被跳过），最终少统计一个组件。

3 小结

感受

遍历链表的题单就做完了，思路很清晰，正常思路去想就没什么问题，无非是map \ set哪个更好是自己实践写代码知道的。（之前在滑窗我只会用map来状态标记）

主要是自己再每个题目有细节，有逻辑要实现好，这一块难度不是很大，基本上就是熟悉语法、数据结构。

-------

ai老师出场，深化我的感悟。

从这道题提炼出的2 个通用解题思维

1.“查询加速” 的选型思维：什么时候用 set/map？什么时候不用？

这道题你一开始想到unordered_map，后来知道unordered_set更优 —— 这个过程就是选型思维的体现。

• 用哈希的核心场景：需要频繁判断 “一个元素是否存在”（比如本题的节点值是否在nums中），且数据量较大（比如本题 n 到 1e4）。
  • 对比：如果用数组遍历查询，时间复杂度是 O (m)（m 是 nums 长度），1e4 数据量下会超时；用哈希是 O (1)，直接最优。
• set vs map 的选型原则：
  • 只需要“存值 + 查询存在性”→ 用unordered_set（更轻量，省空间）；
  • 需要“键值对映射”（比如链表节点值对应出现次数）→ 用unordered_map。

这个思维能直接套用到其他链表题，比如“环形链表 II”“相交链表”里的节点查重，都可以用哈希加速。

2.“状态标记” 的核心思维：用一个布尔变量，解决 “连续段统计” 问题

这道题的核心难点不是 “查询值是否存在”，而是 **“如何统计最长连续段的个数”**—— 你的两个错误，其实都是没吃透这个思维。

• 状态标记的本质：用一个变量（比如is_component）记录当前处于什么状态，通过 “状态的切换” 来触发计数。
  • 本题的状态只有两种：在组件中(true)/不在组件中(false)；
  • 计数的唯一触发时机：false → true（从非组件进入组件，代表新组件开始）；
  • 状态重置时机：true → false（遇到不在 nums 中的节点，组件中断）。