1. 题目描述

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

示例 1：

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

示例 2：

  1. 输入:
  2. head: 0->1->2->3->4
  3. G = [0, 3, 1, 4]
  4. 输出: 2
  5. 解释:
  6. 链表中，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. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val) {
    4. *     this.val = val;
    5. *     this.next = null;
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @param {number[]} G
    11. * @return {number}
    12. */
    13. var numComponents = function(head, G) {
    14.   let cur = head
    15.   let isComponent = false
    16.   let res = 0
    18.   while(cur){
    19.       if(G.indexOf(cur.val) > -1){
    20.           if(!isComponent){
    21.               isComponent = true
    22.               res++
    23.           }
    24.       }else{
    25.           isComponent = false
    26.       }
    27.       cur = cur.next
    28.   }
    29.   return res
    30. };

    4. 提交结果

    image.png