What is the most efficient approach for Linked List Components?

Use a hash set to store nums and scan the linked list once, counting new components when a node is in nums but the previous node is not.

How does the array scanning plus hash lookup pattern apply here?

It lets you iterate through the linked list and check membership in constant time, avoiding nested loops and reducing complexity.

Can a single node in nums be a connected component?

Yes, any node in nums with no consecutive neighbors in nums forms its own single-node component.

What if nums contains all linked list nodes?

The entire linked list becomes a single connected component because all nodes are consecutive in nums.

How do I handle the last node in the list?

Check if it is in nums and whether the previous node is not in nums; if so, increment the component count appropriately.

#817

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

链表组件

给定链表头结点 head ，该链表上的每个结点都有一个唯一的整型值。同时给定列表 nums ，该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。示例 1：输入: head = [0…

数组哈希表链表

题目描述

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

示例 1：

输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

提示：

链表中节点数为n
1 <= n <= 10⁴
0 <= Node.val < n
Node.val 中所有值不同
1 <= nums.length <= n
0 <= nums[i] < n
nums 中所有值不同

lightbulb

解题思路

方法一：哈希表 + 链表一次遍历

题目中需要判断链表中节点的值是否在数组 nums 中，因此我们可以使用哈希表 $s$ 存储数组 nums 中的值。

然后遍历链表，找到第一个在哈希表 $s$ 中的节点，然后从该节点开始遍历，直到遇到不在哈希表 $s$ 中的节点，这样就找到了一个组件，然后继续遍历链表，直到遍历完整个链表。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为链表的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for singly-linked list.
# 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:
        ans = 0
        s = set(nums)
        while head:
            while head and head.val not in s:
                head = head.next
            ans += head is not None
            while head and head.val in s:
                head = head.next
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the length of the linked list and m is the length of nums, because each node is visited once and hash lookups are constant time. Space complexity is O(m) to store the hash set of nums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting clear identification of consecutive sequences in the linked list.
question_mark
Looking for efficient use of hash table to check membership instead of nested loops.
question_mark
Watching for correct handling of isolated nodes versus multi-node components.

warning

常见陷阱

外企场景

error
Using nested loops to compare each node with nums, causing O(n*m) time complexity.
error
Failing to increment the count correctly when a sequence ends or a single node is a component.
error
Ignoring edge nodes or empty nums arrays leading to incorrect component counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting connected components in a linked list with duplicate values allowed.
arrow_right_alt
Returning the actual sublists forming each connected component rather than just the count.
arrow_right_alt
Extending the problem to a doubly linked list and detecting bi-directional connectivity.

help

常见问题

外企场景

继续练习

#706 设计哈希映射 #705 设计哈希集合 #815 公交路线