# [LC] 25.Reverse Nodes in k-Group (Hard, Recursive, LinkedList)

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.

• Could you solve the problem in `O(1)` extra memory space?
• You may not alter the values in the list’s nodes, only nodes itself may be changed.
``````/**
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 reverse(ListNode start, ListNode end){
ListNode prev = null, next;
// prev = null;
//prev.next = start; // prev.next = 4
while(prev != end){ // 4
next = start.next;
start.next = prev;
prev = start;
start = next;
}
return end;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode tmp = new ListNode(0);
root = tmp;
int cnt = 1;
ListNode prev, prev_prev = null;
while(curr != null){
if(cnt % k == 0){
ListNode tmp_next = curr.next;
reverse(prev, curr);
if(prev_prev == null){
tmp.next = curr;
}else{
prev_prev.next = curr;
}
prev.next = tmp_next;
prev_prev = prev;
prev = curr = tmp_next;
}else{
curr = curr.next;
}
cnt++; } return tmp.next;
}
} ``````

Time Complexity: O(N) Space Complexity: O(1)