Welcome to Subscribe On Youtube
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.
-
/** * 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; } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int numComponents(ListNode head, int[] nums) { int ans = 0; Set<Integer> s = new HashSet<>(); for (int v : nums) { s.add(v); } while (head != null) { while (head != null && !s.contains(head.val)) { head = head.next; } ans += head != null ? 1 : 0; while (head != null && s.contains(head.val)) { head = head.next; } } return ans; } }
-
// 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, val=0, next=None): # self.val = val # self.next = next class Solution: def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int: ans = 0 s = set(nums) while head: while head and head.val not in s: head = head.next ans += head is not None while head and head.val in s: 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
-
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func numComponents(head *ListNode, nums []int) int { s := map[int]bool{} for _, v := range nums { s[v] = true } ans := 0 for head != nil { for head != nil && !s[head.Val] { head = head.Next } if head != nil { ans++ } for head != nil && s[head.Val] { head = head.Next } } return ans }
-
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function numComponents(head: ListNode | null, nums: number[]): number { const set = new Set<number>(nums); let res = 0; let cur = head; let inSet = false; while (cur != null) { if (set.has(cur.val)) { if (!inSet) { inSet = true; res++; } } else { inSet = false; } cur = cur.next; } return res; }
-
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number[]} nums * @return {number} */ var numComponents = function (head, nums) { const s = new Set(nums); let ans = 0; while (head) { while (head && !s.has(head.val)) { head = head.next; } ans += head != null; while (head && s.has(head.val)) { head = head.next; } } return ans; };
-
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } use std::collections::HashSet; impl Solution { pub fn num_components(head: Option<Box<ListNode>>, nums: Vec<i32>) -> i32 { let set = nums.into_iter().collect::<HashSet<i32>>(); let mut res = 0; let mut in_set = false; let mut cur = &head; while let Some(node) = cur { if set.contains(&node.val) { if !in_set { in_set = true; res += 1; } } else { in_set = false; } cur = &node.next; } res } }