Title: Linked List Components Source: leetcode.com
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:
|
1 2 3 4 5 6 7 8 |
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:
|
1 2 3 4 5 6 7 8 |
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 by head, 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.
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
''' https://leetcode.com/problems/linked-list-components/ ''' # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def numComponents(self, head, G): """ :type head: ListNode :type G: List[int] :rtype: int """ temp = head lst = [] G = set(G) li = 0 while temp: if temp.val in G: lst.append([temp.val, li]) temp = temp.next li += 1 #print lst p = lst[0] c = 1 for l in lst[1:]: if l[1] - p[1] != 1: c += 1 p = l return c |