LeetCode 817 - Linked List Components

https://leetcode.com/articles/linked-list-components/

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Instead of thinking about connected components in G, think about them in the linked list. Connected components in G must occur consecutively in the linked list.

Scanning through the list, if node.val is in G and node.next.val isn't (including if node.next is null), then this must be the end of a connected component.

• Time Complexity: $O(N + G\text{.length})$, where $N$ is the length of the linked list with root node head.
• Space Complexity: $O(G\text{.length})$, to store Gset.

    public int numComponents(ListNode head, int[] G) {

        Set<Integer> Gset = new HashSet();

        for (int x: G) Gset.add(x);

        ListNode cur = head;

        int ans = 0;

        while (cur != null) {

            if (Gset.contains(cur.val) &&

                    (cur.next == null || !Gset.contains(cur.next.val)))

                ans++;

            cur = cur.next;

        }

        return ans;

    }

Use the first node of the consecutive nodes to determine whether count++. 

public int numComponents(ListNode head, int[] G) {

if (head == null || G == null) {

return 0;

}

int count = 0;

// Set<int[]> set = Stream.of(G).collect(Collectors.toSet());

Set<Integer> set = Arrays.stream(G).boxed().collect(Collectors.toSet());

// new HashSet<Integer>(Arrays.asList(G));

boolean exist = false;// better name

while (head != null) {

if (set.contains(head.val)) {

if (!exist) {

exist = true;

count++;

} // else do nothing

} else {

exist = false;

}

head = head.next; // don't forget this

}

return count;

}

http://zxi.mytechroad.com/blog/graph/leetcode-817-linked-list-components/

Graph Traversal using DFS

  int numComponents(ListNode* head, vector<int>& G) {

    unordered_set<int> f(G.begin(), G.end());

    unordered_map<int, vector<int>> g;

    int u = head->val;

    while (head->next) {

      head = head->next;

      int v = head->val;

      if (f.count(v) && f.count(u)) {

        g[u].push_back(v);

        g[v].push_back(u);

      }

      u = v;

    }

    int ans = 0;

    unordered_set<int> visited;

    for (int u : G) {      

      if (visited.count(u)) continue;

      ++ans;

      dfs(u, g, visited);

    }

    return ans;

  }

private:

  void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) {

    if (visited.count(cur)) return;

    visited.insert(cur);

    for (const int next : g[cur])

      dfs(next, g, visited);    

  }