0817. Linked List Components

题目信息

题号:

0817

难度:

Medium

主题:

链表、集合、连续节点段

原题:

LeetCode 0817

重点:

组件由链表中相邻且值都属于 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,因此它单独构成一个连通组件。