HARD
DATA STRUCTURES AND ALGORITHMS

# How to Solve Reverse Nodes in k-Group

Written By ## Reverse Nodes in k-Group Introduction

The Reverse Nodes in k-Group problem asks us to reverse the nodes of the given linked list k at a time and return the modified list. This problem can be solved using a recursive approach.

## Reverse Nodes in k-Group Problem

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 Inputs and Outputs

#### 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]

## Reverse Nodes in k-Group Solutions

To solve this problem, we use a recursive approach. We go through the linked list, considering k nodes at a time. If there are fewer than k nodes remaining, we leave them as they are without reversing. However, when we have k nodes, we reverse them by changing their next pointers. This reversal process involves carefully keeping track of the previous and next pointers.

Once we reverse the k nodes, the head of the reversed portion becomes the last node of the original k nodes, and we update its next pointer to point to the result of reversing the remaining list. We repeat this process until we reach the end of the linked list. By doing this, we gradually reverse the linked list in groups of k nodes.

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

count = 0

# Check if the number of nodes is a multiple of k
while curr and count < k:
curr = curr.next
count += 1

if count < k:  # Number of nodes is less than k

# Reverse the first k nodes
prev = None
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

# Recursively reverse the remaining list

return prev

# Driver code and test cases
# Test Case 1: Reverse groups of 2 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 2 -> 1 -> 4 -> 3 -> 5 -> None
k1 = 2
while reversed_list1:
print(reversed_list1.val, end=" -> ")
reversed_list1 = reversed_list1.next
print("None")

# Test Case 2: Reverse groups of 3 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 3 -> 2 -> 1 -> 4 -> 5 -> None
k2 = 3
while reversed_list2:
print(reversed_list2.val, end=" -> ")
reversed_list2 = reversed_list2.next
print("None")``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where n is the number of nodes in the linked list. In the worst case, we need to reverse all the nodes in the linked list. It's important to note that the algorithm performs a constant amount of work per node, and the number of nodes processed remains the same regardless of the group size k. So, the time complexity does not depend on the value of k.
• Space Complexity: O(1), because regardless of the size of the linked list or the group size, the amount of addition space remains used constant.