模拟

前置知识 : 反转链表、两两交换链表中的节点 。 LeetCode 有相应题目，可以先做。

设置哑结点 ， 便于操作头结点。 翻转至少要 kkk 个结点 ， 先检查剩余结点够不够 kkk 个。 不够 kkk 个就翻转完成了。

翻转分为组内翻转和首尾变向两步 。 如图所示 ， 当 k=3k =3k=3 ， 111 -> 222 -> 333 变成 333 -> 222 -> 111 就是组内翻转 。 OOO -> 333 ， 111 -> 444 就是首尾变向 。

模拟组内翻转 。 对于第一组，组前结点 p=Op=Op=O 。 用 aaa 表示 ppp -> nextnextnext ，bbb 表示 aaa -> nextnextnext ，ccc 表示 bbb -> nextnextnext 。 让 bbb -> next=anext = anext=a 完成反向 ， a=b,b=ca=b , b=ca=b,b=c 让 a、ba、ba、b 后移。组内 kkk 个点之间的连接线一共 k−1k-1k−1 条，循环 k−1k-1k−1 次 ， 完成组内翻转 。

组内翻转的最后 ， aaa 为组内第一个结点 ， bbb 为下一组的第一个结点 ， 组前结点 ppp 的指向没有变过 ， ppp -> nextnextnext 依然指向翻转前的第一个点 ，所以首尾变向很容易完成 ， 见代码。

代码展示

C++

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {auto dummy = new ListNode(-1);dummy->next = head;auto p= dummy;while(1){auto t = p;for(int i = 0;inext;//检查k个结点够不够。if(!t) break;//剩余结点不足k个auto a = p->next , b = a->next;for(int i = 0;iauto c = b->next;b->next = a;a = b , b = c;}auto c = p->next;p->next = a, c ->next = b;p = c;}return dummy->next;}
};

1. 时间复杂度 : O(n)O(n)O(n) ， nnn 是链表长度，翻转链表的时间复杂度 O(n)O(n)O(n) ，遍历链表的时间复杂度O(n)O(n)O(n) ， 二者是相加关系 ， 每个结点最多被遍历两遍 ， 总时间复杂度 O(2n)O(2n)O(2n) ， 忽略常数时间复杂度 O(n)O(n)O(n) 。
2. 空间复杂度: O(1)O(1)O(1) ， 除若干变量占用的常量级空间，没有使用额外的线性空间

AC