ReverseNodesKGroup_Recursion.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //Reverse elements in link list
    ListNode* reverseList(ListNode* head){
        ListNode* currentNode = NULL;
        //Current Node which stores the reversed head
        while(head!=NULL){
            ListNode* next = head->next;
            head->next = currentNode;
            currentNode = head;
            head = next;         
        }
        return currentNode;
        
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL)
            return NULL;
        
        ListNode* pointer = head;
        //Get K elements out of group
        int i = k;
        while(i - 1 > 0){
            pointer = pointer->next;
            if(pointer == NULL)
                return head;
            i--;
        }
        //Save pointer-> next, this is the next head
        ListNode* tempNode = pointer->next;
        //Break the K elements from the whole link list
        pointer->next = NULL;       
        ListNode* currentNode = reverseList(head);
        //Recursively sort the next K elements
        head->next = reverseKGroup(tempNode,k);
        return currentNode;
    }
};