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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    pair<ListNode*, int> cutList(ListNode* head, int k){
        int cnt = 0;
        ListNode* p = head;
        ListNode* pre = NULL;
        while(p != NULL){
            cnt ++;
            pre = p;
            p = p -> next;
            if(cnt == k) break;
        }
        return {pre, cnt};
    }
    ListNode* reverseList(ListNode* head){
        ListNode* pre = NULL;
        ListNode* p = head;
        while(p != NULL){
            ListNode* nxt = p -> next;
            p -> next = pre;
            pre = p;
            p = nxt;
        }
        return pre;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(k == 0) return head;
        ListNode* cur = head;
        ListNode* dummyHead = new ListNode(-1);
        ListNode* preLast = dummyHead;
        while(cur != NULL){
            pair<ListNode*, int> pir = cutList(cur, k);
            ListNode* tail = pir.first;
            int cnt = pir.second;
            if(cnt < k){ //最后链表剩余个数不足k，保持原样
                preLast -> next = cur;
                break;
            }
            ListNode* nxt = tail -> next;
            tail -> next = NULL;
            preLast -> next = tail;
            preLast = cur;
            reverseList(cur);
            cur = nxt;
        }
        return dummyHead -> next;
    }
};