LeetCode 25. K 个一组翻转链表（***）

题目类型

1. 链表
2. k组翻转

题目链接

https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

此时看起来不难，实际实现的时候很容易出错，建议多刷几次

1. 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
2. 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来

   auto c = b->next, b->next = a

3. k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
4. 继续以上操作

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy;;)
        {
            // 判断是否满足k个元素
            auto q = p;
            for (int i = 0; i < k && q; i ++) q = q->next;
            if (!q) break; // 不满足直接跳出


            // 满足有k个元素
            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
            {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto t = p->next;
            p->next = a;
            t->next = b;
            p = t;
        }
        return dummy->next;
    }
};