[LeetCode] Reverse Nodes in k-Group

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

问题描述：给定一个链表，将它以k个节点为一组，每组中的节点进行你序，返回改变后的链表。

如果节点数不是k的整数倍，剩余节点就保持不变，不能改变节点中的值域，可以改变节点。空间复杂度为O(1)。

思路：用一个指针p遍历链表，另一个指针q指向p的下一个节点，然后用q往后遍历，并用cnt计数，如果后面有p后面没有k个元素则推出循环，如果p后面有k个元素，就用q将p后面的k-1节点取出来，放到p的前面，当插入第一个k-1个节点时，将q放到head之前就行，可以用head来操作，之后的话，就必须用一个prev节点来定位q要插入的位置，开始prev指向p的前面的指针，q就插入到p的前面，prev的后面，之后，q就插入到prev的后面。

class Solution {  
public:  
    ListNode *reverseKGroup(ListNode *head, int k) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int cnt = 0;  
        bool fst = true;  
        ListNode *p = head, *q = NULL, *prev = NULL;  
        while(p) {  
            q = p->next;  
            cnt = 0;  
            while(q && cnt < k - 2) {  
                q = q->next;  
                ++cnt;  
            }  
              
            if(q == NULL)  
                return head;  
              
            cnt = 0;  
            while(cnt < k - 1) {  
                q = p->next;  
                p->next = q->next;  
                if(fst) {  
                    q->next = head;  
                    head = q;  
                }  
                else {  
                    q->next = prev->next;  
                    prev->next = q;  
                }  
                ++cnt;  
            }  
            fst = false;  
            prev = p;  
            p = p->next;  
        }  
          
        return head;  
    }  
};