# Solution For Reverse Nodes In K Group

The problem “Reverse Nodes in K-Group” asks us to reverse each group of k nodes in a linked list such that the nodes in a group are linked in reverse order. If the number of nodes in the last group is less than k, we should leave those nodes as they are.

We can solve this problem by following a recursive approach. We’ll use a recursive function that takes the head of a linked list and the value of k as input. The function will reverse the first group of k nodes and call itself recursively for the remaining part of the list. The base condition for the function will be when the list has less than k nodes, in which case we’ll just return the head of the list.

Here’s how we can implement this approach:

1. Define the recursive function `reverseKGroup(head, k)`, where `head` is the head of the linked list and `k` is the group size.
2. Create a variable called `count` and initialize it to 0. Also create a variable called `current` and initialize it to `head`.
3. Traverse the list using a while loop until the end of the list or until `count == k`.
4. Inside the loop, increment `count` and move `current` to the next node.
5. Check if `count == k`. If it is, we’ll reverse the current group of k nodes.
6. To reverse the current group, we’ll define a new variable called `prev` and initialize it to None. Also create a variable called `next` and initialize it to None.
7. While `count > 0`, do the following:
8. Set `next` to `current.next`.
9. Set `current.next` to `prev`.
10. Set `prev` to `current`.
11. Set `current` to `next`.
12. Decrement `count`.
13. After reversing the group, set `head.next` to `reverseKGroup(current, k)`.
14. Return `prev` as the new head of the reversed group.

Here’s the Python implementation of the recursive approach:

`def reverseKGroup(head, k): count = 0 current = head while current and count < k: current = current.next count += 1 if count == k: # Reverse the current group prev, next = None, None current = head while count > 0: next = current.next current.next = prev prev = current current = next count -= 1 # Recursively call for rest of the list head.next = reverseKGroup(current, k) # Return the new head of the reversed group return prev else: # Base case, list has less than k nodes return head`

That’s it! We’ve successfully solved the “Reverse Nodes in K-Group” problem using a recursive approach.

## Step by Step Implementation For Reverse Nodes In K Group

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
}

ListNode dummy = new ListNode(0);
ListNode prev = dummy;

while (curr != null) {
int i = 0;
while (curr != null && i < k) {
curr = curr.next;
i++;
}

if (i == k) {
ListNode next = curr;
curr = prev.next;
i = 0;

while (i < k) {
next = curr.next;
curr.next = prev.next;
prev.next = curr;
curr = next;
i++;
}

prev = curr;
curr = next;
}
}

return dummy.next;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# reverse nodes in k groups and return the head of the new list
# edge case: if k is 1 or 0, then the list does not need to be reversed
if k <= 1:

# create a dummy node to use as the head of the new list
dummy = ListNode()
prev = dummy

# reverse the nodes in each group of k
# reverse the next k nodes
prev, end = self.reverse(prev, head, k)
# set head to the node after the end of the current group

return dummy.next

# reverse the next k nodes starting at head
# return the new head and end of the reversed group

# edge case: if there are fewer than k nodes remaining, do not reverse them

# set the end node to be the kth node
for i in range(k-1):
# if there are fewer than k nodes remaining, do not reverse them
if not end or not end.next:
return (prev, end)
end = end.next

# reverse the next k nodes
next = curr.next
while curr != end:
temp = next.next
next.next = curr
curr.next = end.next
prev.next = next
next = temp
curr = prev.next

return (prev, curr)```
```Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

Example:

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
// reverse first k nodes
let next = null;
let prev = null;
let count = 0;

while (current !== null && count < k) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}

// next is now a pointer to (k+1)th node
// recursively call for the list starting from current
// and make rest of the list as next of first node
if (next !== null) {
}

// prev is now head of input list
return prev;
};```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int num=0;
while(cur = cur->next)
num++;
while(num>=k) {
cur = pre->next;
nex = cur->next;
for(int i=1;inext=nex->next;
nex->next=pre->next;
pre->next=nex;
nex=cur->next;
}
pre = cur;
num-=k;
}
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
//edge case
if(head == null || k <= 1){
}

ListNode dummy = new ListNode(-1);
ListNode prev = dummy, curr = head;

//reverse k nodes for each iteration
while(curr != null){
int count = 1;
//check if there are k nodes left to reverse
while(curr.next != null && count < k){
curr = curr.next;
count++;
}
//if there are not k nodes left, return the current head
if(count < k){
return dummy.next;
}
//store the next node to reverse
ListNode next = curr.next;
//reverse the current k nodes
curr.next = null;
ReverseList(prev, next);
//move the pointers
curr = next;
}
return dummy.next;
}

//helper function to reverse a singly linked list
private ListNode ReverseList(ListNode prev, ListNode next){
//edge case
if(prev == null || prev.next == null){
return prev;
}
ListNode curr = prev.next;
ListNode last = prev.next;
while(curr != null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
//set the end of the reversed list to point to the next node to reverse
last.next = next;
//set the head of the reversed list to the previous node
return prev;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]