题解 | #链表中的节点每k个一组翻转#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    
    pair<ListNode*,ListNode*> reverseLocal(ListNode* front,ListNode* tail){
        ListNode* pre = nullptr;
        ListNode* cur = front;
        while(cur!=tail){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        cur->next = pre;
        return {cur,front};
    }
    
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        ListNode* pre;
        ListNode* front;
        ListNode* tail;
        ListNode* succ;
        
        pre = dummy;
        front = head;
        while(1){
        //跳出条件
            for(int i = 0 ; i <= k ; i++){
                if(!cur)
                    return dummy->next;
                if(i == k){
                    // update tail && succ
                    tail = cur;
                    succ = cur->next;
                    break;
                }
                cur = cur->next;
            }
            
            // disconnect the region from origin linkedlist
            pre->next = nullptr;
            tail->next = nullptr;
            
            // reverseLocal
            auto tmp = reverseLocal(front,tail);
            
            // update front & tail
            front = tmp.first;
            tail = tmp.second;

            // concat the region into origin linkedlist
            pre->next = front;
            tail->next = succ;
            
            // update pre && front && cur
            pre = tail;
            front = pre->next;
          	// the last cur has been moved to the location of 'front', let the cur points to the location of 'tail'            
          	cur = tail;

        }
    }
};