# 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

| Item | Meaning |
|---|---|
| Input | `head` of a linked list and an array `nums` |
| Output | Number of connected components |
| Node values | Unique integers |
| Connection rule | Two `nums` values are connected if adjacent in the linked list |
| Component | A maximal consecutive run of nodes whose values are in `nums` |

## Examples

Example 1:

```python
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:

```python
[0, 1]
```

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

```python
[3]
```

The answer is:

```python
2
```

Example 2:

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

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

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

The consecutive groups are:

```python
[0, 1]
[3, 4]
```

So the answer is:

```python
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:

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

If we extract only values from `nums`, we get:

```python
[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:

```python
current node is in nums
```

and:

```python
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:

```python
values = set(nums)
```

Initialize:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Build the set, then traverse the linked list once |
| Space | `O(m)` | Store the values from `nums` in a set |

## Implementation

```python
# 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:

```python
values = set(nums)
```

We walk through the list with a pointer:

```python
node = head
```

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

```python
current_in = node.val in values
```

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

```python
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:

```python
if current_in and not next_in:
    answer += 1
```

Finally, move to the next node:

```python
node = node.next
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[0,1,2,3]`, `[0,1,3]` | Official example with two components |
| `[0,1,2,3,4]`, `[0,3,1,4]` | Official example with separated groups |
| Single node | Minimum linked list |
| One middle value | Single isolated component |
| Non-adjacent selected values | Multiple single-node components |
| All nodes selected | One large component |