题解 | #牛群的重新分组#

考察知识点： 链表、链表反转

题目分析：

 首先找到一个组中的最后一个节点，即从头节点开始往下走k - 1个节点，这组从头节点到我们找到的最后一个节点间的所有节点是一组。例如{1,2,3,4,5,6,7,8},3

 接着，将该段链表翻转。翻转时需要记录一个节点的前驱和后继节点。记录前驱节点是为了翻转时将节点n的指向前驱节点，记录后继节点是为了能让节点n再更新到反转前链表中n的下一个节点。

 翻转时，只需要将n的next指针更改即可

 然后要更新n、prev、next的值

 重复上述过程，直到n指向了pnext,即n指向了不属于该组的节点。

 在将一组翻转后，可以将pnext作为头节点，递归调用reverseKGroup函数来处理下一组所有节点。

 注意翻转链表后head变成了尾结点，p变成了头节点，返回时应返回头节点，往后插入时应从尾结点向后插入。

所用语言： C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指kk定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if (head == nullptr) return nullptr;
        ListNode* p = head;
        for (int i = 0; p && i < k - 1; i++) {
            p = p->next;
        }
        if (!p) return head;  //如果最后一组没有k个节点，就返回头节点即可
        //翻转head到p
        ListNode* prev = nullptr;
        ListNode* n = head;
        ListNode* next = n->next;
        ListNode* pnext = p->next;
        while (n != pnext) {
            n->next = prev;
            prev = n;
            n = next;
            if (next) next = next->next;
        }
        head->next = reverseKGroup(pnext, k);
        return p;
    }
};