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.

&nbsp;
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]


&nbsp;
Constraints:


	The number of nodes in the list is n.
	1 &lt;= k &lt;= n &lt;= 5000
	0 &lt;= Node.val &lt;= 1000


&nbsp;
Follow-up: Can you solve the problem in O(1) extra memory space?

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

        # Intialize the result and the current node to the head
        res = node = head

        # Initialize the index of the current node to 0
        i = 0

        # Initialize the head and tail of the reversed nodes group to None
        reversedHead, reversedTail = None, None

        # Initialize the tail of the previous group to None
        previousTail = None

        # Iterate through all nodes
        while node:

            # When we reach the first node in a group
            if i % k == 0:

                # If there is a previous group, connect its tail to the current node
                # This is the case when we have less than k nodes left
                if previousTail:
                    previousTail.next = node

                # Initialize the head and tail of the reversed nodes group
                reversedHead = reversedTail = ListNode(node.val)

            # Continue to reverse subsequent nodes
            else:
                reversedHead = ListNode(node.val, reversedHead)

            # If we are able to reach the last node in a reversed nodes group
            if i % k == k - 1:

                # If there is a previous group, connect its tail to the current node
                # This is the case when we have k nodes and thus, we should reverse this group
                if previousTail:
                    previousTail.next = reversedHead

                # Set the tail of the previous group to the tail of the reversed nodes group
                previousTail = reversedTail

            # Set the head of the first reversed nodes group as the result
            if i == k - 1:
                res = reversedHead

            # Continue to the next node
            i, node = i + 1, node.next

        return res
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int numOfNodes = count(head);
        ListNode ptr = null;
        List<ListNode> start = new ArrayList<>(), end = new ArrayList<>();
        ListNode f = null;
        while (head != null) {
            if (numOfNodes >= k) {
                start.add(head);
                int count = 0;
                while (count < k) {
                    ListNode temp = head.next;
                    head.next = ptr;
                    ptr = head;
                    head = temp;
                    count++;
                }
                end.add(ptr);
                ptr = null;
                numOfNodes -= count;
            }
            else {
                f = head;
                break;
            }
        }
        int n = start.size();
        for (int i = 0; i < n - 1; i++) start.get(i).next = end.get(i + 1);
        start.get(n - 1).next = f;
        return end.get(0);
    }
    public int count(ListNode head) {
        ListNode temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}
class Solution {
    pair<ListNode* , ListNode*> get_rev_list(ListNode* root){
        ListNode *tail = root;
        ListNode *curr = root , *temp , *prev = NULL;
        
        while(curr != NULL){
            temp = curr -> next;
            curr -> next = prev;
            
            prev = curr;
            curr = temp;
        }
        
        return make_pair(prev , tail);
    }
    
    public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k == 1)
            return head;
        
        vector<pair<ListNode* , ListNode*>> store;
        
        ListNode *temp = head , *temp_head = head;
        int len = 0;
        
        while(temp != NULL){
            len++;
            
            if(len == k){
                ListNode *next_head = temp -> next;
                temp -> next = NULL;
                
                store.push_back(get_rev_list(temp_head));
                temp = next_head;
                len = 0;
                temp_head = next_head;
            }
            else
                temp = temp -> next;
        }
        
        if(len == k)
        store.push_back(get_rev_list(temp_head));
        
        for(int i = 1; i < store.size(); i++)
            store[i - 1].second -> next = store[i].first;
        
        if(len != k)
            store[store.size() - 1].second -> next = temp_head;
        
        return store[0].first;
    }
};
var reverseKGroup = function(head, k) {
    const helper = (node) => {
        let ptr = node;
        
        let t = k;
        let prev = null;
        
        while(t && ptr) {
            prev = ptr;
            ptr = ptr.next;
            t -= 1;
        }
        
        if(t > 0) //if k is not zero then do not reverse, simply return;
            return node;
        
        let f = prev.next;
        prev.next = null;
        
        let [rev, end] = reverseList(node);
        
        end.next = helper(f);
        
        return rev;
    }
    
    return helper(head);
};

var reverseList = function(head) {
        let prev = null;
        let current = head;
        let end = head;

        while(current) {
            let next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return [prev, end];
 };
Reverse Nodes in k-Group