2021-03-23 | 817. 链表组件

我会带着你远行 2022-11-12 10:59 26阅读 0赞

### 1. 题目描述 ###

给定链表头结点 `head`，该链表上的每个结点都有一个 **唯一的整型值** 。  
同时给定列表 `G`，该列表是上述链表中整型值的一个子集。  
返回列表 `G` 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 `G` 中）构成的集合。

**示例 1：**

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

**示例 2：**

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

**提示：**

*  如果 `N` 是给定链表 `head` 的长度，`1 <= N <= 10000`。
 *  链表中每个结点的值所在范围为 `[0, N - 1]`。
 *  `1 <= G.length <= 10000`
 *  `G` 是链表中所有结点的值的一个子集.

### 2. 解题思路 ###

对于这道题目。有两个关键点：

*  组件必须是链表中的连续节点
 *  在G中包含连续节点的每个数值，如果出现不连续，结果就+1

根据这两点，我们可以定义一个表示，这里暂且定义名为isComponent，如果当前G中有这个值，并且isComponent是false，就说明这是一个新的组件，结果加一，如果G中不存在这个值，直接将isComponent置位false，将指针向后移动一位，继续遍历。只要当前指针存在，就一直遍历，直到遍历完整个链表。

**复杂度分析：**

*  时间复杂度：O(m+n)，这里需要遍历完整个整个链表和数组，所以时间复杂度为O(m+n)，其中m是链表的元素个数，n是G的元素个数；
 *  空间复杂度：O(1)，这里只需要常量的空间来保存当前指针的引用地址和组件标识符，所以空间复杂度为O(1)。

### 3. 代码实现 ###

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number[]} G * @return {number} */
    var numComponents = function(head, G) { 
        let cur = head
        let isComponent = false
        let res = 0
    
        while(cur){ 
            if(G.indexOf(cur.val) > -1){ 
                if(!isComponent){ 
                    isComponent = true
                    res++
                }
            }else{ 
                isComponent = false
            }
            cur = cur.next
        }
        return res
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210323223225442.png]

[20210323223225442.png]: /images/20221022/5ebfc5ca04714d208d52abb2077f9d50.png?