Linked List Components: Counting Connected Subgroups

Linked List Components is LeetCode 817. You are given the head of a linked list and an array nums that is a subset of the linked list's values. Your task is to count how many connected components are formed by the nodes whose values appear in nums.

Two nodes belong to the same connected component if they are adjacent in the linked list and both have values in nums. If a node in nums is next to a node that is not in nums, it either starts a new component or ends the current one.

Why this problem matters

This problem tests whether you can think about connectivity in a linear structure. It is a graph-flavored question dressed up as a linked list traversal. The "connected components" terminology might remind you of Union-Find or BFS on a grid, but the linked list structure makes things much simpler. You only need to walk forward.

The real skill being tested here is translating a graph concept (connected components) into a linear scan with a membership check. That pattern, using a set for O(1) lookups while traversing a sequence, shows up constantly in interviews.

The key insight

You do not need to build a graph. You do not need Union-Find. You do not need BFS. All you need to do is walk through the linked list from head to tail and count how many times you enter a new group of consecutive nodes that are in nums.

A new connected component starts every time the current node is in nums and the previous node was either not in nums or did not exist (i.e., the current node is the head). That is it. One pass through the list, one set lookup per node.

Solution approach

1. Convert nums into a set for O(1) membership testing.
2. Walk the linked list node by node.
3. Track whether the previous node was in the set.
4. Every time the current node is in the set and the previous node was not, you have found the start of a new connected component. Increment your counter.
5. Return the counter when you reach the end of the list.

The logic is clean because the linked list gives you a fixed traversal order. Two nodes in nums are in the same component if and only if every node between them in the list is also in nums. So you just need to detect the boundaries, the transitions from "not in set" to "in set."

Python solution

def numComponents(head, nums):
    G = set(nums)
    count = 0
    prev_in_G = False

    curr = head
    while curr:
        if curr.val in G:
            if not prev_in_G:
                count += 1
            prev_in_G = True
        else:
            prev_in_G = False
        curr = curr.next

    return count

Visual walkthrough

Let's trace through the list 0 -> 1 -> 2 -> 3 -> 4 with nums = [0, 1, 3]. Watch how the algorithm detects each new component by tracking whether the previous node was in the set.

Two transitions from "not in G" to "in G" means two connected components. The answer is 2.

Complexity analysis

Where n is the number of nodes in the linked list. You cannot do better than O(n) time because you must visit every node at least once. The set is necessary for constant-time lookups; without it, checking membership in nums would cost O(m) per node, where m is the length of nums.

The building blocks

This problem combines two fundamental patterns. Recognizing them helps you solve similar problems faster.

Pattern 1: Hash set membership

Converting a list to a set for O(1) lookups is one of the most common optimizations in interview problems. You see it in Two Sum, Contains Duplicate, Longest Consecutive Sequence, and dozens of others. Whenever you need to repeatedly check "is this value in my collection?", a hash set is almost always the right tool.

Pattern 2: Counting transitions in a linear scan

Instead of explicitly grouping items, you count the number of times a condition starts being true. This is the same idea behind counting words in a sentence (count transitions from space to non-space), counting islands in a 1D array, or counting runs of consecutive characters. You only need to track the previous state and compare it to the current state.

Edge cases

• Every node is in nums. The entire list is one connected component. The algorithm enters "in G" at the head and never leaves. Count = 1.
• No nodes are in nums. The algorithm never enters "in G." Count = 0.
• Single node in nums. If that node is in the list, it forms one component by itself. Count = 1.
• Alternating pattern. If nums contains every other node (e.g., nodes 0, 2, 4 in a list 0-1-2-3-4), each node in nums is its own component because non-G nodes separate them.
• nums contains all nodes except one. The missing node splits the list into at most two components.

From understanding to recall

This problem is a good example of a solution that feels obvious once you see it, but is tricky to reconstruct from scratch. The details matter: do you increment the counter when you enter a group or when you leave it? Do you need to handle the last group separately? (No, because you count on entry, not exit.)

The best way to lock this in is spaced repetition. Solve it once today, again in two days, again in a week. By the third rep, the pattern of "set lookup plus transition counting" will feel automatic, and you will recognize it instantly in similar problems.

Related posts

• Linked List Cycle - Another linked list traversal problem that uses a clever scanning technique instead of brute force
• Number of Islands - The classic connected components problem on a 2D grid, solved with DFS flood fill
• Remove Duplicates from Sorted List - A simpler linked list traversal that also requires tracking what you saw on the previous step