# LeetCode #25: Reverse Nodes in k-Group

Hello, coding enthusiasts! Today, we’re solving the “Reverse Nodes in k-Group” problem from LeetCode. This problem is a great exercise in linked list manipulation and recursion.

We’re given a linked list and a number `k`, and we need to reverse the nodes of the list `k` at a time. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

The catch is that we can’t modify the values in the list’s nodes, only the nodes themselves may be changed.

Let’s dive into the problem!

## Problem Statement

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list.

`k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

``````Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]``````

Example 2:

``````Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]``````

## Constraints

• The number of nodes in the list is `n`.
• `1 <= k <= n <= 5000`
• `0 <= Node.val <= 1000`

## Approach

The problem can be solved using a recursive approach. Here are the steps:

1. Base Case: If the list is empty or has less than k nodes, we return the list as it is.
2. Reverse k Nodes: We reverse the first k nodes of the list.
3. Recursive Call: We make a recursive call to the rest of the list and attach it to the end of the reversed list.
4. Return New Head: Finally, we return the new head of the list.

## Time Complexity

The time complexity of this approach is `O(n)`, where n is the number of nodes in the list. This is because we are processing each node exactly once.

## Space Complexity

The space complexity is `O(n)`, due to the recursive stack. In the worst case, the depth of the recursive call stack will be `n/k`, which is `O(n)`.

## Code

### Python

Python
``````class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# Base case
for _ in range(k):
if not node:
node = node.next

# Reverse k nodes
for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node

# Recursive call to the rest of the list and attach it to the end of the reversed list

# Now the head is the last node of the reversed list
return prev``````

### JavaScript

JavaScript
``````var reverseKGroup = function(head, k) {
// Base case
for (let i = 0; i < k; i++) {
if (!node) {
}
node = node.next;
}

// Reverse k nodes
let prev = null;
for (let i = 0; i < k; i++) {
let nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}

// Recursive call to the rest of the list and attach it to the end of the reversed list

// Now the head is the last node of the reversed list
return prev;
};``````

## Conclusion

In this post, we tackled the “Reverse Nodes in k-Group” problem from LeetCode. We used a recursive approach to reverse the nodes in k-group.

The time complexity of this approach is `O(n)`, and the space complexity is also `O(n)` due to the recursive stack.

Happy coding! 