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

- Define the recursive function
`reverseKGroup(head, k)`

, where`head`

is the head of the linked list and`k`

is the group size. - Create a variable called
`count`

and initialize it to 0. Also create a variable called`current`

and initialize it to`head`

. - Traverse the list using a while loop until the end of the list or until
`count == k`

. - Inside the loop, increment
`count`

and move`current`

to the next node. - Check if
`count == k`

. If it is, we’ll reverse the current group of k nodes. - 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. - While
`count > 0`

, do the following: - Set
`next`

to`current.next`

. - Set
`current.next`

to`prev`

. - Set
`prev`

to`current`

. - Set
`current`

to`next`

. - Decrement
`count`

. - After reversing the group, set
`head.next`

to`reverseKGroup(current, k)`

. - 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

/** * Definition for singly-linked list. * 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) { if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode curr = head; 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: return head # create a dummy node to use as the head of the new list dummy = ListNode() dummy.next = head prev = dummy # reverse the nodes in each group of k while head: # reverse the next k nodes prev, end = self.reverse(prev, head, k) # set head to the node after the end of the current group head = end.next return dummy.next def reverse(self, prev, head, k): # 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 if not head or not head.next: return (prev, head) # set the end node to be the kth node end = head 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 curr = head 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: Given this linked list: 1->2->3->4->5 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. /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var reverseKGroup = function(head, k) { // reverse first k nodes let current = head; 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) { head.next = reverseKGroup(next, k); } // prev is now head of input list return prev; };

/** * Definition for singly-linked list. * 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) { if(head==NULL || k==1) return head; int num=0; ListNode *preheader = new ListNode(-1); preheader->next = head; ListNode *cur = preheader, *nex, *pre = preheader; 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; } return preheader->next; } };

/** * Definition for singly-linked list. * 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){ return head; } ListNode dummy = new ListNode(-1); dummy.next = head; 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 prev = head; curr = next; head = 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; } }