25.K个一组翻转链表

在完成前置题目"92. 反转链表 II - 力扣（LeetCode）"的基础上，我们需要进一步考虑链表长度是否满足K个一组翻转的条件。若剩余链表长度不足K，则无需进行翻转。

具体实现步骤如下：

1. 首先计算链表的长度
2. 以K个节点为一组进行链表翻转。与92题不同的是，本题可能涉及多次翻转操作。每次翻转完成后，需要将已翻转部分与剩余链表进行正确衔接。

见下图

        翻转后的链表是怎么的出来的呢？接下来我们详细分解：

        第一步：翻转1，2

        理解第一步操作后，后续步骤基本相同。需要注意的是，在每组翻转前，需将 p0 移动到下一组翻转起始节点的前一个位置。以当前为例，下一组翻转的起始节点是 3，因此 p0 应移动到 1 的位置。值得注意的是，1 正是 p0->next 的指向。由于 p0->next 需要被修改（用于连接 1 和 3，即 p0->next->next = cur），同时 p0 需要指向当前的头节点 pre（即 p0->next = pre），因此需要特别关注这一操作。

        具体代码：

/*** 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(0,head);ListNode *p0 = dummy;ListNode *cur = head;int len = 0;while (cur){len++;cur = cur->next;}while (len >= k) {len -= k;ListNode *pre = nullptr;ListNode *cur = p0->next;for (int i = 1;i <= k;i++) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}ListNode *nxt = p0->next;p0->next->next = cur;p0->next = pre;p0 = nxt;}ListNode *ans = dummy->next;delete dummy;return ans;}
};

         时间复杂度：O(n) n为链表的长度

        空间复杂度：O(1)，仅用到若干额外的变量