reverseKGroup.cpp

// https://leetcode.com/problems/reverse-nodes-in-k-group/

/*  Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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 nodes, only nodes itself may be changed.
 *
 *  Only constant memory is allowed.
 *
 *  For 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 
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// recursively
class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            int len=0;
            for(auto p=head; p; p=p->next, len++);
            if(len<k) 
                return head;
            ListNode *cur=head, *pre=nullptr, *next;
            for(int i=0; i<k; i++){
                next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            ListNode* newhead = reverseKGroup(cur, k);
            head->next = newhead;
            return pre;
        }
};

// Accepted