leetcode-25. 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.

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.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

题目要求k个一组进行翻转，其实实质是指针的指向问题，“先连后断”是基本的原则，这里的先连指的是k块整体先于后面的k+1

相连接，然后在操作k块内的指针，最后解决k块前的指针问题。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode res(0);
        ListNode* l = &res;
        ListNode  **p = new ListNode*[k];
        bool flag = false;
        ListNode *f=head;
        for(int i=0;i<k;i++){
            if(f){
                f = f->next;
            }else{
                flag = true;//只有少于k个指针
                break;
            }
        }
        if(flag){
            return head;
        }
        
        //初始化
        l->next = head;
        
        while(!flag){
            p[0] = l->next;
            for(int i=1;i<=k-1;i++){
                p[i]=p[i-1]->next;
            }//初始化
            
            p[0]->next = p[k-1]->next;
            for(int i=k-1;i>=1;i--){
                p[i]->next = p[i-1];
            }
            l->next = p[k-1];
            l = p[0];
            
            f = p[0]->next;
            for(int i=0;i<k;i++){
                if(f){
                    f = f->next;
                }else{
                    flag = true;//只有少于k个指针
                    break;
                }
            }
        }
        
        return res.next;
    }
};