题目描述
思路解析动画文字版
记住「值入集合 O(1) 判断；只在组件尾节点计数」，下面每帧都在套它。
准备 · 集合内节点标蓝：先把 nums={0,1,3,4,6,8} 装进集合，链表里值在集合中的节点全部标蓝。接下来从头扫，只在每段蓝色的「最后一个」节点计数。
扫描 · 节点 0：cur 走到节点 0。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 0：节点 0 在集合，下一个 1 也在集合，组件还没结束，先不计数，等走到它的尾节点再数。
扫描 · 节点 1：cur 走到节点 1。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 1 是组件尾：节点 1 在集合，但下一个节点 2 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 1。
扫描 · 节点 2：cur 走到节点 2。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
判定 · 节点 2：节点 2 不在集合，不可能是组件的一部分，组件数不变，继续往后。
扫描 · 节点 3：cur 走到节点 3。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 3：节点 3 在集合，下一个 4 也在集合，组件还没结束，先不计数，等走到它的尾节点再数。
扫描 · 节点 4：cur 走到节点 4。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 4 是组件尾：节点 4 在集合，但下一个节点 5 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 2。
扫描 · 节点 5：cur 走到节点 5。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
判定 · 节点 5：节点 5 不在集合，不可能是组件的一部分，组件数不变，继续往后。
扫描 · 节点 6：cur 走到节点 6。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 6 是组件尾：节点 6 在集合，但下一个节点 7 不在集合，说明一段连续的蓝色到此为止，这是组件的尾，组件数加一变成 3。
扫描 · 节点 7：cur 走到节点 7。它不是蓝色，值不在集合里，直接跳过，它还能把两个组件隔开。
判定 · 节点 7：节点 7 不在集合，不可能是组件的一部分，组件数不变，继续往后。
扫描 · 节点 8：cur 走到节点 8。它是蓝色的，值在集合里，可能是某个组件的一部分。
判定 · 节点 8 是组件尾：节点 8 在集合，且它已经是最后一个节点，一个组件到此结束，组件数加一变成 4。
完成：全链表扫完，一共在 4 个组件尾节点上计了数，所以组件数 = 4。分别是 [0,1]、[3,4]、[6]、[8]，每段连续的蓝色就是一个组件。
边界先想清：单节点、空集合、全连续。
面试重点是讲清「尾节点计数不重不漏」的正确性。
参考代码
from typing import List, Optionalclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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 ans复杂度
- 时间：O(n + m)，建集合 O(m) + 扫链表 O(n)
- 空间：O(m)，哈希集合存 nums 的 m 个值
易错点
面试追问把动画讲成自己的话
追问为什么「只在尾节点计数」是对的？
追问能否不建集合、原地判断？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
链表中的下一个更大节点
LeetCode 1019 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题