题目描述
这是 LeetCode 上的 25. K 个一组翻转链表 ，难度为 困难。
Tag : 「递归」、「迭代」、「链表」
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5] 复制代码
示例 2：
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5] 复制代码
示例 3：
输入：head = [1,2,3,4,5], k = 1 输出：[1,2,3,4,5] 复制代码
示例 4：
输入：head = [1], k = 1 输出：[1] 复制代码
提示：
- 列表中节点的数量在范围 sz 内
- 1 <= sz <= 5000
- 0 <= Node.val <= 1000
- 1 <= k <= sz
迭代解法（哨兵技巧）
哨兵技巧我们在前面的多道链表题讲过，让三叶来帮你回忆一下：
做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。
链表和树的题目天然适合使用递归来做。
但这次我们先将简单的「递归版本」放一放，先搞清楚迭代版本该如何实现。
我们可以设计一个翻转函数 reverse ：
传入节点 root 作为参数，函数的作用是将以 root 为起点的 kkk 个节点进行翻转。
当以 root 为起点的长度为 kkk 的一段翻转完成后，再将下一个起始节点传入，直到整条链表都被处理完成。
当然，在 reverse 函数真正执行翻转前，需要先确保节点 root 后面至少有 kkk 个节点。
我们可以结合图解再来体会一下这个过程：
假设当前样例为 1->2->3->4->5->6->7 和 k = 3 ：
然后我们调用 reverse(cur, k)，在 reverse() 方法内部，几个指针的指向如图所
示，会通过先判断 cur 是否为空，从而确定是否有足够的节点进行翻转：
然后先通过 while 循环，将中间的数量为 k - 1 的 next 指针进行翻转：
最后再处理一下局部的头结点和尾结点，这样一次 reverse(cur, k) 执行就结束了：
回到主方法，将 cur 往前移动 k 步，再调用 reverse(cur, k) 实现 k 个一组翻转：
代码：
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode cur = dummy; while (cur != null) { reverse(cur, k); int u = k; while (u-- > 0 && cur != null) cur = cur.next; } return dummy.next; } // reverse 的作用是将 root 后面的 k 个节点进行翻转 void reverse(ListNode root, int k) { // 检查 root 后面是否有 k 个节点 int u = k; ListNode cur = root; while (u-- > 0 && cur != null) cur = cur.next; if (cur == null) return; // 进行翻转 ListNode tail = cur.next; ListNode a = root.next, b = a.next; // 当需要翻转 k 个节点时，中间就有 k - 1 个 next 指针需要翻转 while (k-- > 1) { ListNode c = b.next; b.next = a; a = b; b = c; } root.next.next = tail; root.next = a; } } 复制代码
- 时间复杂度：会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
递归解法
搞懂了较难的「迭代哨兵」版本之后，常规的「递归无哨兵」版本写起来应该更加容易了。
需要注意的是，当我们不使用「哨兵」时，检查是否足够 kkk 位，只需要检查是否有 k−1k - 1k−1 个 nextnextnext 指针即可。
代码：
class Solution { public ListNode reverseKGroup(ListNode head, int k) { int u = k; ListNode p = head; while (p != null && u-- > 1) p = p.next; if (p == null) return head; ListNode tail = head; ListNode prev = head, cur = prev.next; u = k; while (u-- > 1) { ListNode tmp = cur.next; cur.next = prev; prev = cur; cur = tmp; } tail.next = reverseKGroup(cur, k); return prev; } } 复制代码
- 时间复杂度：会将每个节点处理一遍。复杂度为 O(n)O(n)O(n)
- 空间复杂度：只有忽略递归带来的空间开销才是 O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.25 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
