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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
  
    void reverse(ListNode* head, ListNode* end) {
	 //在第一题的基础上增加边界条件，当head和end相遇时，递归终止
        if (head == nullptr || head->next == nullptr || head == end)
            return ;
        reverse(head->next, end);
        head->next->next = head;
        head->next = nullptr;
        // return new_head;
    }

//上一题中在一个列表的两点之间进行翻转
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int i = 1;
        ListNode* tmp = head;
        ListNode* start = nullptr;
        ListNode* end = nullptr;
        ListNode* pre = nullptr;
        ListNode* after = nullptr;
        while (tmp != nullptr) {
            if (m != 1 && i == m - 1)
                pre = tmp;
            if (i == m) {
                start = tmp;
            }
            if (i == n) {
                end = tmp;
            }
            i++;
            tmp = tmp->next;
        }
        if (end->next != nullptr)
            after = end->next;
        reverse(start, end);
        // cout << start->val <<end;
        if (m != 1) {
            pre->next = end;
            start->next = after;
            return head;
        } else {
            start->next = after;
            return end;
        }
    }
  
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* tmp = head;
        int len = 0;
	  //获取链表的长度
        while(tmp != nullptr){
            len++;
            tmp = tmp->next;
        }
	  //特殊情况处理
        if(head == nullptr || head->next == nullptr || k > len)
            return head;
        int piece = len / k;
	  //第一次反转的结果作为新链表的头结点
        int start = 1,end = k;
        ListNode* new_head =  reverseBetween(head, start, end);
	  //把后面的group依次反转
        for(int i = 1;i < piece;i++){
            reverseBetween(new_head, start + i * k, end+ i * k);
        }
	  返回新的头结点
        return new_head;
    }
};