LeetCode 817: Linked List Components

Problem Restatement

We are given the head of a linked list.

Every node in the linked list has a unique integer value.

We are also given an integer array nums, where every value in nums appears somewhere in the linked list.

Two values from nums are connected if they appear next to each other in the linked list.

Return the number of connected components formed by values in nums. A connected component is a maximal consecutive group of linked list nodes whose values are all in nums. The official statement defines this as counting connected components in nums where two values are connected if they appear consecutively in the linked list.

Input and Output

Examples

Example 1:

head = [0, 1, 2, 3]
nums = [0, 1, 3]

The values 0 and 1 are adjacent in the linked list, so they form one component:

[0, 1]

The value 3 appears alone, so it forms another component:

[3]

The answer is:

2

Example 2:

head = [0, 1, 2, 3, 4]
nums = [0, 3, 1, 4]

The values from nums appear in the linked list like this:

0 -> 1 -> 2 -> 3 -> 4
^    ^         ^    ^

The consecutive groups are:

[0, 1]
[3, 4]

So the answer is:

2

First Thought: Extract and Group

A direct idea is to walk through the linked list and build a new list containing only values that appear in nums.

But this loses the gaps between components.

For example:

head = [0, 1, 2, 3, 4]
nums = [0, 3, 1, 4]

If we extract only values from nums, we get:

[0, 1, 3, 4]

This looks like one list, but 1 and 3 were separated by 2 in the original linked list. They are not connected.

So we should count components directly while traversing the original linked list.

Key Insight

A component ends when the current node is in nums, but the next node is either missing or not in nums.

So we can count component endings.

For each node:

current node is in nums

and:

next node does not exist or next node is not in nums

then this node is the last node of a component, so we increment the answer.

To make membership checks fast, convert nums into a set.

Algorithm

Convert nums to a hash set:

values = set(nums)

Initialize:

answer = 0

Traverse the linked list.

For each node:

1. Check whether node.val is in values.
2. Check whether node.next is missing or node.next.val is not in values.
3. If both are true, increment answer.

Return answer.

Correctness

Every connected component is a maximal consecutive run of linked list nodes whose values are in nums.

Each such run has exactly one final node. That final node has a value in nums, and the node after it either does not exist or has a value outside nums.

The algorithm increments the answer exactly at such final nodes.

It does not increment inside a component, because the next node is also in nums.

It does not increment outside a component, because the current node is not in nums.

Therefore, the algorithm counts every component once and only once.

Complexity

Let n be the number of nodes in the linked list, and let m = len(nums).

Implementation

# 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:
        values = set(nums)
        answer = 0

        node = head

        while node is not None:
            current_in = node.val in values
            next_in = node.next is not None and node.next.val in values

            if current_in and not next_in:
                answer += 1

            node = node.next

        return answer

Code Explanation

The set gives constant-time membership checks:

values = set(nums)

We walk through the list with a pointer:

node = head

For each node, we check whether the current value belongs to nums:

current_in = node.val in values

Then we check whether the next node continues the same component:

next_in = node.next is not None and node.next.val in values

If the current node is in nums but the next node is not, then the current component ends here:

if current_in and not next_in:
    answer += 1

Finally, move to the next node:

node = node.next

Testing

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    tail = dummy

    for value in values:
        tail.next = ListNode(value)
        tail = tail.next

    return dummy.next

def run_tests():
    s = Solution()

    assert s.numComponents(build_list([0, 1, 2, 3]), [0, 1, 3]) == 2
    assert s.numComponents(build_list([0, 1, 2, 3, 4]), [0, 3, 1, 4]) == 2
    assert s.numComponents(build_list([0]), [0]) == 1
    assert s.numComponents(build_list([0, 1, 2]), [1]) == 1
    assert s.numComponents(build_list([0, 1, 2, 3]), [0, 2]) == 2
    assert s.numComponents(build_list([0, 1, 2, 3]), [0, 1, 2, 3]) == 1

    print("all tests passed")

run_tests()