817. Linked List Components

• 817. Linked List Components
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

Pitfall

这题不能说是陷阱，第一感觉就是union find，其实有一边过的solution

从左往右扫，检查是否这一段都在G里面

Solution

  public int numComponents(ListNode head, int[] G) {
    final Set<Integer> setG = new HashSet<>();

    for (int i : G) {
      setG.add(i);
    }
    ListNode cur = head;
    int res = 0;
    while (cur != null) {
      if (setG.contains(cur.val) && (cur.next == null || !setG.contains(cur.next.val))) res++;
      cur = cur.next;
    }
    return res;
  }