题目链接 · 灵神原题解（署名来源）

前置题目

1. 206. 反转链表
2. 92. 反转链表 II

视频讲解

请看【基础算法精讲 06】。制作不易，欢迎点赞~

写法一

Python 解法1

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 统计节点个数
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next

        # last_tail 是上一组翻转后的尾节点
        last_tail = dummy = ListNode(next=head)

        # k 个一组处理
        while n >= k:
            n -= k

            pre = None
            cur = last_tail.next
            for _ in range(k):  # 同 92 题
                nxt = cur.next
                cur.next = pre  # 每次循环只修改一个 next，方便大家理解
                pre = cur
                cur = nxt

            # 请结合视频中的图理解
            # 翻转后：
            # pre 是当前组的头节点
            # cur 是下一组的起始节点
            # last_tail 是上一组的尾节点
            # last_tail.next 是当前组的尾节点
            tail = last_tail.next
            tail.next = cur  # 当前组的尾节点指向下一组的起始节点
            last_tail.next = pre  # 上一组的尾节点指向当前组的头节点
            last_tail = tail

        return dummy.next

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 统计节点个数
        int n = 0;
        for (ListNode* cur = head; cur; cur = cur->next) {
            n++;
        }

        ListNode dummy(0, head);
        ListNode* last_tail = &dummy; // 上一组翻转后的尾节点

        // k 个一组处理
        for (; n >= k; n -= k) {
            ListNode* pre = nullptr;
            ListNode* cur = last_tail->next;
            for (int i = 0; i < k; i++) { // 同 92 题
                ListNode* nxt = cur->next;
                cur->next = pre; // 每次循环只修改一个 next，方便大家理解
                pre = cur;
                cur = nxt;
            }

            // 请结合视频中的图理解
            // 翻转后：
            // pre 是当前组的头节点
            // cur 是下一组的起始节点
            // last_tail 是上一组的尾节点
            // last_tail->next 是当前组的尾节点
            ListNode* tail = last_tail->next;
            tail->next = cur; // 当前组的尾节点指向下一组的起始节点
            last_tail->next = pre; // 上一组的尾节点指向当前组的头节点
            last_tail = tail;
        }

        return dummy.next;
    }
};

写法二

不需要先统计节点个数。对于每一组，我们可以先试探性地往前走 $k$ 步，如果发现剩余节点不足 $k$ 个，则直接返回答案。

Python 解法3

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # last_tail 是上一组翻转后的尾节点
        last_tail = dummy = ListNode(next=head)

        # k 个一组处理
        while True:
            # 看看这一组是否有 k 个节点
            cur = last_tail
            for _ in range(k):
                cur = cur.next
                if cur is None:  # 不足 k 个节点
                    return dummy.next

            pre = None
            cur = last_tail.next
            for _ in range(k):  # 同 92 题
                nxt = cur.next
                cur.next = pre  # 每次循环只修改一个 next，方便大家理解
                pre = cur
                cur = nxt

            # 请结合视频中的图理解
            # 翻转后：
            # pre 是当前组的头节点
            # cur 是下一组的起始节点
            # last_tail 是上一组的尾节点
            # last_tail.next 是当前组的尾节点
            tail = last_tail.next
            tail.next = cur  # 当前组的尾节点指向下一组的起始节点
            last_tail.next = pre  # 上一组的尾节点指向当前组的头节点
            last_tail = tail

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0, head);
        ListNode* last_tail = &dummy; // 上一组翻转后的尾节点

        // k 个一组处理
        while (true) {
            // 看看这一组是否有 k 个节点
            ListNode* cur = last_tail;
            for (int i = 0; i < k; i++) {
                cur = cur->next;
                if (cur == nullptr) { // 不足 k 个节点
                    return dummy.next;
                }
            }

            ListNode* pre = nullptr;
            cur = last_tail->next;
            for (int i = 0; i < k; i++) { // 同 92 题
                ListNode* nxt = cur->next;
                cur->next = pre; // 每次循环只修改一个 next，方便大家理解
                pre = cur;
                cur = nxt;
            }

            // 请结合视频中的图理解
            // 翻转后：
            // pre 是当前组的头节点
            // cur 是下一组的起始节点
            // last_tail 是上一组的尾节点
            // last_tail->next 是当前组的尾节点
            ListNode* tail = last_tail->next;
            tail->next = cur; // 当前组的尾节点指向下一组的起始节点
            last_tail->next = pre; // 上一组的尾节点指向当前组的头节点
            last_tail = tail;
        }
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是链表节点个数。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府