25.K 个一组翻转链表

给你链表的头节点 head ，每 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]

提示：

• 链表中的节点数目为 n
• $1\le k\le n\le 5000$
• $0\le Node.val\le 1000$

进阶： 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

解法一(迭代+模拟)

思路分析

1. 因为题目要求尝试只用 $O(1)$ 的额外空间的算法来解决; 所以暂时先不考虑递归或者使用数组等数据结构;
2. 根据题目意思, 每k个链表节点为一段进行反转, 然后剩余不足k个的节点则保持原有顺序不进行反转;
3. 所以可以考虑一边遍历链表, 一边对链表进行分段, 然后对每段链表进行反转, 再将反转好的链表链接到一起即可;

实现代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;  // 遍历节点
        int n = 0;  // 记录每组长度
        ListNode start = head;  // 记录每组反转链表的起始位置
        ListNode end = null;    // 记录新链表的最末尾位置
        ListNode newStart = null;   // 记录新链表的起始位置
        boolean isFirst = true; // 记录当前组是否为第一组
        while (p != null) {
            ++ n;
            if (n % k == 0) {
                ListNode t = p.next;    // 缓存下一组的起始节点
                p.next = null;
                if (isFirst) {
                    // 当前为第一组反转链表
                    newStart = reverseList(start);
                    isFirst = false;
                    // 更新末尾指针
                    end = getEnd(newStart);
                } else {
                    // 当前不为第一组反转链表 则接续在第一组反转链表末尾后
                    end.next = reverseList(start);
                    end = getEnd(end);
                }
                // 更新下一组起始节点
                p = t;
                start = t;
            } else {
                p = p.next;
            }
        }
        end.next = start;
        return newStart;
    }
    // 反转单个链表
    private ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p = null;
        ListNode q = head;
        while (q != null) {
            ListNode t = q.next;    // 提前记录下一个要反转的节点
            q.next = p;     // 反转节点
            p = q;      // 更新新的头节点
            q = t;      // 继续往下反转
        }
        return p;
    }
    // 获取当前段链表的末尾节点
    private ListNode getEnd(ListNode head) {
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
}

运行结果

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:43.3 MB,击败了26.03% 的Java用户

复杂度分析

• 时间复杂度: 需要整体遍历一遍链表, 每遍历一组,则需要对该组链表进行反转, 反转时间复杂度为 $O(k)$, 然后需要遍历获取每组末尾节点, 时间复杂度也为 $O(k)$, 总共有 $\frac{n}{k}$ 组, 即整体时间复杂度为 $O((k+k)\times \frac{n}{k})$, 为 $O(n\times k)$
• 空间复杂度: 只使用了有限变量,即为 $O(1)$

解法二(递归)

实现思路

1. 同样也可以用递归来实现
2. 先遍历得到一组链表节点, 然后执行反转逻辑, 再继续递归反转下一组链表

实现代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode p = head;
        int len = 1;
        // 遍历获得一组链表
        while (p != null && p.next != null && len < k) {
            ++ len;
            p = p.next;
        }
        if (len < k) {
            // 剩余链表不足为一组 不进行反转
            return head;
        }
        // 执行反转
        ListNode pre = null;
        ListNode q = head;
        ListNode nextStart = p.next;  // 此处先保存下一组链表起始节点 避免反转过程p.next出现变化
        while (q != nextStart) {
            ListNode t = q.next;
            q.next = pre;
            pre = q;
            q = t;
        }
        // 此时head为新的末尾节点
        // 继续反转下一组 并链接到上一组的末尾节点
        head.next = reverseKGroup(nextStart, k);
        return pre;
    }
    
}

运行结果

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:43.2 MB,击败了75.01% 的Java用户

复杂度分析

• 时间复杂度: $O(n\times k)$
• 空间复杂度: $O(\frac{n}{k})$