Formatted question description: https://leetcode.ca/all/817.html
817. Linked List Components (Medium)
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.
Note:
- If
N
is the length of the linked list given byhead
,1 <= N <= 10000
. - The value of each node in the linked list will be in the range
[0, N - 1]
. 1 <= G.length <= 10000
.G
is a subset of all values in the linked list.
Companies:
Google
Related Topics:
Linked List
Solution 1.
// OJ: https://leetcode.com/problems/linked-list-components/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
unordered_set<int> s(G.begin(), G.end());
int ans = 0;
while (true) {
while (head && s.find(head->val) == s.end()) head = head->next;
if (!head) break;
++ans;
while (head && s.find(head->val) != s.end()) head = head->next;
}
return ans;
}
};
Java
-
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int numComponents(ListNode head, int[] G) { Set<Integer> subset = new HashSet<Integer>(); for (int value : G) subset.add(value); boolean inComponent = false; int components = 0; ListNode node = head; while (node != null) { int value = node.val; if (subset.contains(value)) { if (!inComponent) { inComponent = true; components++; } } else { if (inComponent) inComponent = false; } node = node.next; } return components; } }
-
// OJ: https://leetcode.com/problems/linked-list-components/ // Time: O(N) // Space: O(N) class Solution { public: int numComponents(ListNode* head, vector<int>& G) { unordered_set<int> s(G.begin(), G.end()); int ans = 0; while (true) { while (head && s.find(head->val) == s.end()) head = head->next; if (!head) break; ++ans; while (head && s.find(head->val) != s.end()) head = head->next; } return ans; } };
-
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def numComponents(self, head, G): """ :type head: ListNode :type G: List[int] :rtype: int """ groups = 0 subset = set(G) while head: if head.val in subset and (not head.next or head.next.val not in subset): groups += 1 head = head.next return groups