# LeetCode 25: Reverse Nodes in k-Group

## Problem Restatement

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

We need to reverse the nodes of the list `k` at a time and return the modified list.

If the number of remaining nodes at the end is fewer than `k`, those nodes must stay in the same order.

We may not change node values. We may only change node links.

For example:

```text
1 -> 2 -> 3 -> 4 -> 5
k = 2
```

becomes:

```text
2 -> 1 -> 4 -> 3 -> 5
```

The constraints say `1 <= k <= n <= 5000`, and node values are between `0` and `1000`. The follow-up asks for `O(1)` extra memory.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list and integer `k` |
| Output | Head after reversing every complete group of `k` nodes |
| Short final group | Leave unchanged |
| Node values | Must not be modified |
| Constraint | `1 <= k <= n <= 5000` |

Example function shape:

```python
def reverseKGroup(head: ListNode, k: int) -> ListNode:
    ...
```

## Examples

Example 1:

```text
head = [1,2,3,4,5]
k = 2
```

Reverse each complete group of two:

```text
[1,2] -> [2,1]
[3,4] -> [4,3]
[5]   -> unchanged
```

Output:

```text
[2,1,4,3,5]
```

Example 2:

```text
head = [1,2,3,4,5]
k = 3
```

Reverse the first three nodes:

```text
[1,2,3] -> [3,2,1]
```

Only two nodes remain, so they stay unchanged:

```text
[4,5]
```

Output:

```text
[3,2,1,4,5]
```

## First Thought: Copy Values Into an Array

One easy idea is:

1. Copy all node values into an array.
2. Reverse every group of `k` values.
3. Write the values back into the linked list.

This is simpler than pointer manipulation.

But the problem forbids changing values only. We must change the nodes themselves.

So this approach does not satisfy the requirement.

## Key Insight

We can process one group at a time.

For each group:

1. Check whether there are at least `k` nodes.
2. Reverse exactly those `k` nodes.
3. Connect the reversed group back to the previous part and the next part.
4. Move to the next group.

A dummy node helps with the first group because the head changes after reversal.

Before reversing one group:

```text
group_prev -> 1 -> 2 -> 3 -> next_group
```

For `k = 3`, after reversing:

```text
group_prev -> 3 -> 2 -> 1 -> next_group
```

The node `1`, which was the old group head, becomes the tail of the reversed group.

## Visual Walkthrough

Use:

```text
head = 1 -> 2 -> 3 -> 4 -> 5
k = 2
```

Create:

```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
```

First group:

```text
1 -> 2
```

Reverse it:

```text
2 -> 1
```

Reconnect:

```text
dummy -> 2 -> 1 -> 3 -> 4 -> 5
```

Now `group_prev` becomes `1`.

Second group:

```text
3 -> 4
```

Reverse it:

```text
4 -> 3
```

Reconnect:

```text
dummy -> 2 -> 1 -> 4 -> 3 -> 5
```

Only one node remains:

```text
5
```

Since fewer than `k` nodes remain, leave it unchanged.

Final result:

```text
2 -> 1 -> 4 -> 3 -> 5
```

## Algorithm

1. Create a dummy node pointing to `head`.
2. Let `group_prev = dummy`.
3. Repeatedly find the `k`th node after `group_prev`.
4. If no `k`th node exists, stop.
5. Let `group_next = kth.next`.
6. Reverse nodes from `group_prev.next` up to before `group_next`.
7. Reconnect the reversed group:
   - old group head becomes group tail
   - `group_prev.next` becomes the new group head
8. Move `group_prev` to the tail of the reversed group.
9. Return `dummy.next`.

## Correctness

At the start of each iteration, all nodes before `group_prev` have already been processed correctly.

The algorithm first checks whether a complete group of `k` nodes exists. If fewer than `k` nodes remain, it stops and leaves them unchanged, as required.

For a complete group, the algorithm reverses exactly the nodes from `group_prev.next` through the `k`th node. It uses `group_next` as the boundary, so nodes after the group are not changed.

After reversal, the old group head becomes the group tail, and the old `k`th node becomes the group head. The algorithm reconnects the previous processed part to the new group head and reconnects the new group tail to the next unprocessed part.

Then `group_prev` moves to the tail of the reversed group, so the invariant holds for the next group.

Therefore every complete group of `k` nodes is reversed exactly once, and the final incomplete group remains unchanged.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited a constant number of times |
| Space | `O(1)` | Only pointer variables are used |

## Implementation

```python
from typing import Optional

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

class Solution:
    def reverseKGroup(
        self,
        head: Optional[ListNode],
        k: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            kth = self.get_kth(group_prev, k)

            if not kth:
                break

            group_next = kth.next

            prev = group_next
            current = group_prev.next

            while current != group_next:
                temp = current.next
                current.next = prev
                prev = current
                current = temp

            old_group_head = group_prev.next
            group_prev.next = kth
            group_prev = old_group_head

        return dummy.next

    def get_kth(
        self,
        current: Optional[ListNode],
        k: int
    ) -> Optional[ListNode]:
        while current and k > 0:
            current = current.next
            k -= 1

        return current
```

## Code Explanation

Create a dummy node:

```python
dummy = ListNode(0, head)
```

This handles reversal of the first group.

`group_prev` points to the node before the group we want to reverse:

```python
group_prev = dummy
```

Find the `k`th node after `group_prev`:

```python
kth = self.get_kth(group_prev, k)
```

If there are fewer than `k` nodes left:

```python
if not kth:
    break
```

Save the node after the group:

```python
group_next = kth.next
```

Reverse the group using standard linked-list reversal:

```python
prev = group_next
current = group_prev.next
```

The boundary is `group_next`, so the loop reverses only the current group:

```python
while current != group_next:
    temp = current.next
    current.next = prev
    prev = current
    current = temp
```

After reversal, `kth` is the new head of the group.

The old group head becomes the tail:

```python
old_group_head = group_prev.next
```

Reconnect the previous part:

```python
group_prev.next = kth
```

Move to the next group:

```python
group_prev = old_group_head
```

Finally:

```python
return dummy.next
```

## Testing

```python
def build_list(values):
    dummy = ListNode()
    current = dummy

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

    return dummy.next

def to_list(head):
    result = []

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

    return result

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.reverseKGroup(head, 2)) == [2, 1, 4, 3, 5]

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.reverseKGroup(head, 3)) == [3, 2, 1, 4, 5]

    head = build_list([1, 2, 3, 4])
    assert to_list(s.reverseKGroup(head, 4)) == [4, 3, 2, 1]

    head = build_list([1, 2, 3])
    assert to_list(s.reverseKGroup(head, 1)) == [1, 2, 3]

    head = build_list([1])
    assert to_list(s.reverseKGroup(head, 1)) == [1]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3,4,5]`, `k = 2` | Standard pair reversal |
| `[1,2,3,4,5]`, `k = 3` | Final short group remains unchanged |
| `[1,2,3,4]`, `k = 4` | Whole list is one group |
| `[1,2,3]`, `k = 1` | No visible change |
| `[1]`, `k = 1` | Smallest valid list |