0. 题目

Reference: 如何k个一组反转链表 - labuladong的算法小抄 (gitbook.io)

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

比如 1 -> 2 -> 3 -> 4 -> 5 这个链表两个一组反转，就得到 2 -> 1 -> 4 -> 3 -> 5。

举例：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

输入：head = [1], k = 1
输出：[1]

提示：

• 列表中节点的数量在范围 sz 内
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz

递归 or 迭代？

链表是一种兼具递归和迭代性质的数据结构，递归性质的题目是什么样的呢？

之前的文章有提到过：

1. 大问题可以拆成两个子问题

2. 子问题的求解方式和大问题一样

3. 存在最小子问题

在这个例子里面，最小子问题就是当节点数量小于 k 的时候，返回原样。

假设 k = 2，有一个节点的时候，直接返回；有两个节点的时候，我们要反转这两个节点；有三个节点的时候，我们反转前两个，第三个不变。

也就是说，第三个节点的处理方法和最小子问题一样（保持不变）。

这是从最小子问题开始扩展的思考方式，我们也可以从大问题开始思考。

假如我们有10个节点，k = 2，那么我们就要先反转前两个，剩下的8个节点用相同的方式进行反转（子问题=原问题）。

因为子问题和原问题的结构完全相同，这就说明问题具备递归性质。

1. 递归解法

1. 先反转以 head 开头的 k 个节点，返回 result 1；
2. 然后 head = k+1，用相同的方式反转 k 个节点， 返回 result 2；
3. 把 result 1 和 result 2 连起来返回结果。

递归代码

我们之前用递归实现过反转某个区间的节点的代码，现在我们可以稍作修改来解决这个问题。

public ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        return head;
    }
    // 以 head.next 为起点，反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;
    return last;
}

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    if (k == 1) return head;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
  	// 反转前 k 个元素
    ListNode newHead = reverseN(a, k);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}

递归代码分析

这里比较重要的是 reverseKGroup 里面的一个 for loop 判断，目的是搞清楚剩余的节点还有没有 k 个，假如不足，就直接返回 head，跟其他反转的结果相连。

在 reverseN 里面，我们复用了之前的代码，唯一的区别是删掉了 successor 相关的代码，因为我们要在 reverseKGroup 里面进行反转之后的各部分连接（a.next = reverseKGroup(b, k);)

这里其实有两次递归，第一次是 reverseN 里面的递归，反转 a 到 b 之间的节点，返回反转之后的 head；

第二次是 reverseKGroup 里面的递归，我们需要不断重新计算下一个 ab 区间，并且把各个区间相连。

2. 迭代思路

值得注意的是，区间内部的节点反转，我们也可以用迭代的方法来完成。思路是：

设定三个变量，previous，current，next；

previous 初始值为 null；

current 和 next 都等于 head 节点；

当 current 不为 null （也就是链表没有到最后）的时候，进入循环：

• 先找到 next 节点（current.next）；
• 然后把 current 节点的 next 设为 previous 节点（也就是反转的第一步）；
• 接着 previous 节点变成 current（反转的第二步）；
• 然后 current 节点成为 next（移动到下一个节点继续重复循环）；

比如：输入 1 -> 2 -> 3

第一轮初始 (null, 1 -> 2 -> 3)：

• pre = null;
• current = 1;
• next = 1;

第一轮结束 (2 -> 3, 1-> null) ：

• next = 2;
• current.next = pre = null;
• pre = current = 1;
• current = next = 2;

第二轮结束 (2 -> 1 -> null, 3)：

• next = 3;
• current.next = pre = 1;
• pre = current = 2;
• current = next = 3;

第三轮结束 (3 -> 2 -> 1 -> null)：

• next = null;
• current.next = pre = 2;
• pre = current = 3;
• current = next = null;

输出结果：newhead = pre = 3。

代码（反转以 a 为头结点的链表）

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

代码（反转从 a 到 b 之间的节点）

「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」，我们可以用类似的方法来反转 a 到 b 之间的节点，只需要改 while 的终止条件。

// 反转区间 [a, b) 的元素，注意是左闭右开
ListNode reverseBetween(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

为什么是左闭右开？

反转以 a 为头结点的链表里面 b = null，也就是说，b = LastNode.next。

我们只考虑反转该区间，不考虑反转该区间 + LastNode.next，所以右边是开区间。

所以 reverseBetween(ListNode a, ListNode b) 这个方法中的 b 不能理解成 [1, k] 里面的 k，它实际上是 k+1，也就是下一个子区间的 head。

用迭代解决区间内反转，用递归解决区间之间的相连

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素，a + k = b
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverseBetween(a, b);
    // 递归反转后续链表并连接起来，如前面所说，b 是下一个子区间的 head。
    a.next = reverseKGroup(b, k);
    return newHead;
}

3. 复杂度

递归解法：时间复杂度：O(n)，空间复杂度 = O(N)

迭代+递归解法：时间复杂度：O(n)，空间复杂度 = O(N)

4. 结语

这个问题是困难级的，我个人研究之后觉得难点在于以下三个问题：

1. 子区间的反转；
2. 子区间反转结果的相连；
3. 如何判断所剩节点不满 k 个；

第一个问题可以用递归或迭代来解决；

第二个问题用递归来解决（因为我们不知道链表的长度，无法用 for loop 来分割区间）；

第三个问题用 for loop 来解决，通过不断 probe b.next 来确定最后一个节点，通过比较 i 和 k 的大小来判定是否满足所剩区间 < k 这个条件，假如满足，直接返回 head（因为不需要反转不满 k 的部分）。