817. Linked List Components #

Problem #

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 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.

Problem Summary #

The meaning of this problem is not described very clearly. I only understood it after getting WA a few times.

The meaning of this problem is: how many groups of sub-linked lists can be formed in G, with the requirement that these sub-linked lists are ordered in the original linked list.

Solution Approach #

If we abstract this problem a bit further, it becomes this: remove the numbers that do not exist in G from the original linked list, and it will be cut into several linked list segments. For example, mark numbers that exist in G in the original linked list as 0, and numbers that do not exist as 1. If the original linked list is marked as 0-0-0-1-0-1-1-0-0-1-0-1, then the original linked list is cut into 4 segments. As long as we find a 0-1 combination in the linked list, it can be considered one segment, because a segment must have been generated here.

Consider the ending cases: 0-1, 1-0, 0-0, 1-1. The characteristic of these 4 cases is that as long as the last bit is 0, a new segment will be produced. So separately check the end of the linked list once more; if it is 0, add one more.

Code #

package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func numComponents(head *ListNode, G []int) int {
	if head.Next == nil {
		return 1
	}
	gMap := toMap(G)
	count := 0
	cur := head

	for cur != nil {
		if _, ok := gMap[cur.Val]; ok {
			if cur.Next == nil { // If it exists at the end, add one directly
				count++
			} else {
				if _, ok = gMap[cur.Next.Val]; !ok {
					count++
				}
			}
		}
		cur = cur.Next
	}
	return count
}

func toMap(G []int) map[int]int {
	GMap := make(map[int]int, 0)
	for _, value := range G {
		GMap[value] = 0
	}
	return GMap
}