# LeetCode 725: Split Linked List in Parts

## Problem Restatement

We are given the head of a singly linked list and an integer `k`.

We need to split the linked list into `k` consecutive parts.

The parts must follow these rules:

| Rule | Meaning |
|---|---|
| Keep original order | Nodes must appear in the same order as the input list |
| Sizes as equal as possible | No two parts should differ in size by more than `1` |
| Earlier parts are larger | If some parts need one extra node, give it to earlier parts |
| Always return `k` parts | If there are fewer nodes than `k`, some parts are `None` |

Return an array of length `k`, where each item is the head of one part.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head`, the head of a singly linked list |
| Input | Integer `k` |
| Output | A list of `k` linked-list heads |
| Empty part | Represented by `None` |
| Split rule | Parts are consecutive segments of the original list |

The function shape is:

```python
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> list[Optional[ListNode]]:
        ...
```

## Examples

Example 1:

```python
head = [1, 2, 3]
k = 5
```

There are only `3` nodes but we need `5` parts.

So the result is:

```python
[[1], [2], [3], [], []]
```

The last two parts are empty.

Example 2:

```python
head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
```

There are `10` nodes and `3` parts.

Each part gets at least:

```python
10 // 3 = 3
```

There is one extra node:

```python
10 % 3 = 1
```

So the first part gets one extra node.

The result is:

```python
[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
```

## First Thought: Convert to an Array

A simple approach is to copy all linked-list values into an array.

Then compute the size of each part and rebuild new linked lists.

This is easy, but it does extra work and creates new nodes.

The problem asks us to split the original linked list, so we can reuse existing nodes by cutting `next` pointers.

## Key Insight

First count the number of nodes.

Let:

```python
n = length of the linked list
```

Each part should have at least:

```python
base = n // k
```

nodes.

The number of parts that get one extra node is:

```python
extra = n % k
```

So:

| Part Index | Size |
|---:|---:|
| `0` to `extra - 1` | `base + 1` |
| `extra` to `k - 1` | `base` |

Then walk through the linked list and cut each part after its required number of nodes.

## Algorithm

1. Count the total number of nodes `n`.
2. Compute:
   ```python
   base = n // k
   extra = n % k
   ```
3. Create an empty result list.
4. Set `cur = head`.
5. For each part index `i` from `0` to `k - 1`:
   - Set `part_head = cur`.
   - Compute the current part size:
     ```python
     size = base + 1 if i < extra else base
     ```
   - Move `cur` forward `size - 1` times to reach the part tail.
   - Cut the list by setting the tail's `next` to `None`.
   - Move `cur` to the next part head.
   - Append `part_head` to the result.
6. Return the result.

## Correctness

The algorithm first counts the exact number of nodes `n`.

The values `base = n // k` and `extra = n % k` divide the nodes into `k` part sizes whose total is exactly `n`. The first `extra` parts have size `base + 1`, and the remaining parts have size `base`. Therefore no two part sizes differ by more than one, and earlier larger parts come before later smaller parts.

During splitting, the algorithm processes nodes from left to right. For each part, it records the current node as the part head, advances exactly the required number of nodes, and cuts the final node from the rest of the list. This produces a consecutive segment of the original list.

After a part is cut, `cur` moves to the next node, which is the head of the next part. Thus no node is skipped or reused.

If `n < k`, then `base = 0`, so only the first `n` parts receive one node, and the remaining parts receive size `0`, represented by `None`.

Therefore the algorithm returns exactly `k` consecutive parts with valid sizes and original node order.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + k)` | Count nodes, then produce `k` parts |
| Space | `O(k)` | The result array has `k` entries |

The linked-list nodes are reused in place.

## 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 splitListToParts(self, head: Optional[ListNode], k: int) -> list[Optional[ListNode]]:
        n = 0
        cur = head

        while cur:
            n += 1
            cur = cur.next

        base = n // k
        extra = n % k

        result = []
        cur = head

        for i in range(k):
            part_head = cur
            size = base + (1 if i < extra else 0)

            for _ in range(size - 1):
                cur = cur.next

            if cur:
                next_part = cur.next
                cur.next = None
                cur = next_part

            result.append(part_head)

        return result
```

## Code Explanation

First, count all nodes:

```python
n = 0
cur = head

while cur:
    n += 1
    cur = cur.next
```

Then compute the base part size and the number of larger parts:

```python
base = n // k
extra = n % k
```

Start splitting from the original head:

```python
result = []
cur = head
```

For each part, save its head:

```python
part_head = cur
```

Compute this part's size:

```python
size = base + (1 if i < extra else 0)
```

Move to the tail of the part:

```python
for _ in range(size - 1):
    cur = cur.next
```

If the part is non-empty, cut it from the rest of the list:

```python
if cur:
    next_part = cur.next
    cur.next = None
    cur = next_part
```

Finally, store the part head:

```python
result.append(part_head)
```

## Example Walkthrough

Use:

```python
head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
```

Count:

```python
n = 10
```

Compute:

```python
base = 10 // 3 = 3
extra = 10 % 3 = 1
```

Part sizes are:

```python
[4, 3, 3]
```

Split:

| Part | Size | Nodes |
|---:|---:|---|
| `0` | `4` | `[1, 2, 3, 4]` |
| `1` | `3` | `[5, 6, 7]` |
| `2` | `3` | `[8, 9, 10]` |

Return those three heads.

## Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def parts_to_lists(parts):
    return [to_list(part) for part in parts]

def test_split_list_to_parts():
    s = Solution()

    head = build_list([1, 2, 3])
    assert parts_to_lists(s.splitListToParts(head, 5)) == [
        [1],
        [2],
        [3],
        [],
        [],
    ]

    head = build_list([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    assert parts_to_lists(s.splitListToParts(head, 3)) == [
        [1, 2, 3, 4],
        [5, 6, 7],
        [8, 9, 10],
    ]

    head = build_list([])
    assert parts_to_lists(s.splitListToParts(head, 3)) == [
        [],
        [],
        [],
    ]

    head = build_list([1, 2, 3, 4])
    assert parts_to_lists(s.splitListToParts(head, 2)) == [
        [1, 2],
        [3, 4],
    ]

    print("all tests passed")

test_split_list_to_parts()
```

Test coverage:

| Test | Why |
|---|---|
| Fewer nodes than parts | Confirms `None` parts |
| Uneven split | Confirms earlier larger parts |
| Empty list | Confirms all parts are empty |
| Even split | Confirms equal part sizes |