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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    // 第一和函数反转以a为头结点的链表
    ListNode* reverse(ListNode* a) {
        ListNode* pre; // 前一个要拼接的点
        ListNode* cur;  // 当前的点
        ListNode* next;  // 要挪动的下一个点
        pre =nullptr;   
        cur = a;
        next = a;

        while(cur!=nullptr) {
            next = cur->next;
            cur->next=pre;
            pre = cur;
            cur=next;
        }
        return pre;
    }


    // 反转[a,b)区间内的元素
    ListNode* reverse(ListNode* m, ListNode* n) { // 维持区间[m,n)左闭右开的区间大小
        ListNode* pre; // 前一个要拼接的点
        ListNode* cur;  // 当前的点
        ListNode* next;  // 要挪动的下一个点
        pre =nullptr;   
        cur = m;
        next = m;
        while(cur!=n) {
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    // 这个就相当于
    // a->b->c->d->e->f->null   反转 b->c->d   得到的结果就是 d->c->b->nullptr



    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(head==nullptr) {
            return head;
        }
        ListNode* a;
        ListNode* b;
        a=b=head;

        for(int i=0;i<k;i++) {
            if(b==nullptr) {
                return head;
            }
            b=b->next;
        }

        ListNode* new_head = reverse(a,b);
        a->next = reverseKGroup(b, k);
        return new_head;
    }
};