0817. Linked List Components¶
题目信息¶
- 题号:
0817
- 难度:
Medium
- 主题:
链表、集合、连续节点段
- 原题:
- 重点:
组件由链表中相邻且值都属于 nums 的节点形成;相同集合元素在链表中的非连续位置属于不同组件
题目重述¶
给定一条节点值互不相同的单链表 head,以及由其中部分节点值组成的数组 nums。只保留值属于 nums 的节点,并按照原链表的相邻关系判断连通:两个保留节点只有在原链表中直接相邻时才属于同一个组件。
请返回这些节点构成的连通组件数量。组件统计的是链表中的连续节点段,而不是仅按数值集合是否相关来合并。
链表节点数 n 在 [1, 10^4] 范围内,节点值互不相同且位于 [0, n - 1];1 <= nums.length <= n,nums 中元素互不相同并都来自链表。
自建示例¶
多个分离的连续段:
输入:head = [0,1,2,3,4,5], nums = [0,2,3,5]
输出:3
解释:值 0 单独形成一段,值 2 与 3 在链表中相邻形成一段,值 5 单独形成一段,共三个组件。
单节点链表:
输入:head = [0], nums = [0]
输出:1
解释:链表节点数和 nums 长度都达到题目允许的最小值。唯一节点属于 nums,因此它单独构成一个连通组件。