Linked List Components in Java

给定一个单链表的头节点和一个表示节点值子集的整数数组 G。任务是确定链表中包含 G 中值的连接组件的数量。

示例 1

输入

链表：0 -> 1 -> 2 -> 3

子集 G = {0, 1, 3}

输出 2

解释： 组件 {0, 1} 和 {3} 是分开的，因为 2 不在 G 中，中断了连续性。

示例 2

输入

链表：0 -> 1 -> 2 -> 3 -> 4

子集 G = {0, 3, 1, 4}

输出 2

解释： 组件 {0, 1} 和 {3, 4} 是分开的，因为 2 不在 G 中，中断了连续性。

示例 3

输入

链表：1 -> 2 -> 3 -> 4 -> 5

子集 G = {2, 3, 4}

输出 1

解释： 节点 {2, 3, 4} 在列表中是连续的，形成一个连接组件。

方法 1：使用 HashSet 方法

HashSet 方法用于检查节点值是否属于给定的子集 G。

算法

步骤 1： 将 G 的所有值存储在 HashSet 中。

步骤 2： 遍历链表并检查当前节点的值是否存在于 HashSet 中。

步骤 3： 如果当前节点在 G 中，并且其下一个节点不在 G 中（或为 null），则将计数加一，因为它标志着一个连接组件的结束。

步骤 4： 移动到下一个节点并继续该过程。

步骤 5： 返回连接组件的总数。

输出

 
2   

时间复杂度： 程序的 O(n)。这是因为我们遍历了链表一次。

空间复杂度： 程序的 O(k)。这是因为 HashSet 最多存储 G 中的 k 个元素。

方法 2：排序和二分查找方法

在排序数组 G 上使用二分查找，以有效地确定节点值是否是子集的一部分。我们遍历链表，通过检查 G 中的连续节点来计算连接组件的数量。

算法

步骤 1： 对数组 G 进行排序，以便使用二分查找进行快速查找。

步骤 2： 初始化一个计数变量来跟踪组件的数量。

步骤 3： 遍历链表

步骤 3.1： 使用二分查找 (Arrays.binarySearch()) 检查当前节点是否在 G 中。

步骤 3.2： 如果开始了一个新组件（节点在 G 中，但前一个不在），则增加计数。

步骤 3.3： 如果节点不在 G 中，则标记组件的结束。

步骤 4： 返回连接组件的最终计数。

输出

 
2   

时间复杂度： 程序的 O(n log k)。这是因为排序需要 O(k log k)，遍历链表需要 O(n)，二分查找需要 O(log k)。

空间复杂度： 程序的 O(1)。这是因为除了输入存储之外，没有使用额外的空间。