LeetCode 817中等链表/哈希
链表组件 图解题解
这道题到底在问什么
给定链表 head 与数组 nums（nums 的值都在链表中、互不相同）。连续且都属于 nums 的一段节点构成一个组件，返回组件数量。
- 输入
- head=[0,1,2,3], nums=[0,1,3]
- 输出
- 2 （组件 [0,1] 和 [3]）
最优解：一步一步想明白
- 3记住「值入集合 O(1) 判断；只在组件尾节点计数」，下面每帧都在套它。
- 4nums = {0,1,3,4,6,8} 组件数 = 0先把 nums={0,1,3,4,6,8} 装进集合，链表里值在集合中的节点全部标蓝。接下来从头扫，只在每段蓝色的「最后一个」节点计数。
- 5当前值 0 在集合 组件数 = 0cur 走到节点 0。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 6组件内部，暂不计数 组件数 = 0节点 0 在集合，下一个 1 也在集合，组件还没结束，先不计数，等走到它的尾节点再数。
- 7当前值 1 在集合 组件数 = 0cur 走到节点 1。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 8组件尾！组件数 = 1节点 1 在集合，但下一个节点 2 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 1。
- 9当前值 2 不在集合 组件数 = 1cur 走到节点 2。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
- 102 不在集合 → 跳过 组件数 = 1节点 2 不在集合，不可能是组件的一部分，组件数不变，继续往后。
- 11当前值 3 在集合 组件数 = 1cur 走到节点 3。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 12组件内部，暂不计数 组件数 = 1节点 3 在集合，下一个 4 也在集合，组件还没结束，先不计数，等走到它的尾节点再数。
- 13当前值 4 在集合 组件数 = 1cur 走到节点 4。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 14组件尾！组件数 = 2节点 4 在集合，但下一个节点 5 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 2。
- 15当前值 5 不在集合 组件数 = 2cur 走到节点 5。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
- 165 不在集合 → 跳过 组件数 = 2节点 5 不在集合，不可能是组件的一部分，组件数不变，继续往后。
- 17当前值 6 在集合 组件数 = 2cur 走到节点 6。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 18组件尾！组件数 = 3节点 6 在集合，但下一个节点 7 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 3。
- 19当前值 7 不在集合 组件数 = 3cur 走到节点 7。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
- 207 不在集合 → 跳过 组件数 = 3节点 7 不在集合，不可能是组件的一部分，组件数不变，继续往后。
- 21当前值 8 在集合 组件数 = 3cur 走到节点 8。它是蓝色的，值在集合里，可能是某个组件的一部分。
- 22组件尾！组件数 = 4节点 8 在集合，且它已经是最后一个节点，一个组件到此结束，组件数加一变成 4。
- 23组件数 = 4全链表扫完，一共在 4 个组件尾节点上计了数，所以组件数 = 4。分别是 [0,1]、[3,4]、[6]、[8]，每段连续的蓝色就是一个组件。
⚠️ 容易写错的地方
✗ 错：每遇到集合内节点就计数
✓ 对：只在组件「尾」节点计数
否则一个长组件会被重复计数多次
✗ 错：忘了处理最后一个节点
✓ 对：cur.next 为空时也算组件结束
末尾的组件没有「下一个」，要单独算作尾
✗ 错：用数组线性查找判断是否在 nums
✓ 对：用哈希集合 O(1) 判断
线性查找会让整体退化到 O(n·m)
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
values = set(nums)
ans = 0
cur = head
while cur:
if cur.val in values and (cur.next is None or cur.next.val not in values):
ans += 1
cur = cur.next
return ansC++
#include <vector>
#include <unordered_set>
using namespace std;
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> values(nums.begin(), nums.end());
int ans = 0;
for (ListNode* cur = head; cur; cur = cur->next) {
if (values.count(cur->val) && (cur->next == nullptr || !values.count(cur->next->val))) {
++ans;
}
}
return ans;
}
};Java
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> values = new HashSet<>();
for (int x : nums) values.add(x);
int ans = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (values.contains(cur.val) && (cur.next == null || !values.contains(cur.next.val))) {
ans++;
}
}
return ans;
}
}复杂度
时间
O(n + m)
建集合 O(m) + 扫链表 O(n)
空间
O(m)
哈希集合存 nums 的 m 个值
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 链表组件 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「只在尾节点计数」是对的？+
每个组件是一段极大的连续在集合的节点，它有且只有一个尾节点（下一个不在集合或到末尾）。在尾节点计数，等价于「数组件的个数」，既不重复也不遗漏。也可以反过来「只在头节点计数」，对称成立。
能否不建集合、原地判断？+
若 nums 已排序可二分（O(n log m)），但最干净的还是哈希集合 O(n+m)。面试中先给集合解，再讨论排序/位图等空间优化即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 链表组件 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。