25. K 个一组翻转链表

题目描述

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯地改变节点内部的值，而是需要实际进行节点交换。

示例 1

text

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

示例 2

text

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

约束

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶

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

核心思路

这题最重要的是理解两件事：

不是整条链表翻转，而是每 k 个节点翻转一次。
如果最后剩下的节点数不足 k 个，就不要翻。

所以整题的本质是：

先判断当前这一段是否有 k 个节点
如果有，就把这 k 个节点翻转
再把翻转后的这一段，和前后链表重新接起来
然后继续处理下一段

这题至少有两种常见做法：

解法一：迭代分组翻转（推荐，空间最优）
解法二：递归分组翻转

解法一：迭代分组翻转

这是最经典、面试里最推荐的做法。

思路拆解

假设链表是：

text

1 -> 2 -> 3 -> 4 -> 5 -> 6

如果 k = 3，那么我们要做的是：

先翻转 [1,2,3]，得到 3 -> 2 -> 1
再翻转 [4,5,6]，得到 6 -> 5 -> 4
最后接起来：

text

3 -> 2 -> 1 -> 6 -> 5 -> 4

如果链表是：

text

1 -> 2 -> 3 -> 4 -> 5

k = 3 时：

第一组 [1,2,3] 可以翻
第二组只剩 [4,5]，不足 3 个，不翻

结果就是：

text

3 -> 2 -> 1 -> 4 -> 5

这题需要记住的几个指针

在每一组里，我们通常会关心：

groupPrev：当前这一组前面的那个节点
kth：当前这一组的第 k 个节点
groupNext：下一组的起点，也就是 kth.next

翻转完成后：

原来的组头会变成组尾
原来的组尾会变成组头

所以最后要做两件事：

groupPrev.next 指向新的组头
这一组新的组尾指向 groupNext

一步一步写出算法

第一步：先准备虚拟头节点

虚拟头节点 dummy 可以让我们统一处理“第一组翻转后头节点变化”的情况。

const dummy = new ListNode(0, head)
let groupPrev = dummy

第二步：找到当前组的第 `k` 个节点

如果从 groupPrev 开始往后走 k 步都走不到，说明剩余节点不足 k 个，直接结束。

function getKthNode(node: ListNode | null, k: number): ListNode | null {
    while (node !== null && k > 0) {
        node = node.next
        k--
    }
    return node
}

主流程里：

const kth = getKthNode(groupPrev, k)
if (kth === null) {
    break
}

第三步：记录下一组的起点

const groupNext = kth.next

后面翻转这一组时，最终需要把尾巴接回 groupNext。

第四步：翻转当前这一组

我们翻转的是：

text

[groupPrev.next, ..., kth]

翻转时常见写法是：

prev 初始指向 groupNext
cur 初始指向这一组的头
一直翻到 cur === groupNext 为止

let prev: ListNode | null = groupNext
let cur = groupPrev.next

while (cur !== groupNext) {
    const next = cur!.next
    cur!.next = prev
    prev = cur
    cur = next
}

第五步：重新接回链表

翻转前：

groupPrev.next 是这一组的头

翻转后：

kth 变成这一组新的头
原来的组头变成新的尾

所以：

const newGroupTail = groupPrev.next!
groupPrev.next = kth
groupPrev = newGroupTail

为什么最后 groupPrev = newGroupTail？

因为翻完之后，原组头已经变成了这一组的尾节点，下一轮它就会变成“下一组的前驱节点”。

代码实现（TypeScript）

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    const dummy = new ListNode(0, head)
    let groupPrev: ListNode | null = dummy

    const getKthNode = (node: ListNode | null, step: number): ListNode | null => {
        while (node !== null && step > 0) {
            node = node.next
            step--
        }
        return node
    }

    while (groupPrev !== null) {
        const kth = getKthNode(groupPrev, k)
        if (kth === null) {
            break
        }

        const groupNext = kth.next
        let prev: ListNode | null = groupNext
        let cur = groupPrev.next

        while (cur !== groupNext) {
            const next = cur!.next
            cur!.next = prev
            prev = cur
            cur = next
        }

        const newGroupTail = groupPrev.next!
        groupPrev.next = kth
        groupPrev = newGroupTail
    }

    return dummy.next
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

这一解法的优缺点

优点：

满足进阶要求，额外空间是 O(1)
是最标准的写法
面试里最推荐

缺点：

指针比较多，第一次写容易绕
容易在“翻转后接回去”这里写错

解法二：递归分组翻转

这个做法更利于从“问题拆分”的角度理解。

思路拆解

对当前链表头 head 来说：

先看从 head 开始是否有 k 个节点
如果不足 k 个，直接返回 head
如果够 k 个，就先把前 k 个节点翻转
然后递归处理后面的链表
最后把当前这一组翻转后的尾巴，接到后面递归处理好的结果上

本质上就是：

text

当前这一组翻完 + 后面剩余部分递归处理

一步一步写出算法

第一步：先判断够不够 `k` 个节点

我们先用一个指针往后走 k 步。

let cur = head
for (let i = 0; i < k; i++) {
    if (cur === null) {
        return head
    }
    cur = cur.next
}

如果过程中遇到 null，说明不足 k 个，不翻。

第二步：先递归处理后面的部分

这里 cur 走完后，正好指向“下一组的起点”。

const rest = reverseKGroup(cur, k)

第三步：翻转当前前 `k` 个节点

当前要翻的是从 head 到 cur 前面的这段。

翻转时：

prev 初始指向已经处理好的后半段 rest
node 从 head 开始往后走
一共翻 k 次

let prev = rest
let node = head

for (let i = 0; i < k; i++) {
    const next = node!.next
    node!.next = prev
    prev = node
    node = next
}

翻完之后：

prev 就是当前这一组新的头

第四步：返回新的组头

return prev

代码实现（TypeScript）

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let cur = head
    for (let i = 0; i < k; i++) {
        if (cur === null) {
            return head
        }
        cur = cur.next
    }

    const rest = reverseKGroup(cur, k)
    let prev = rest
    let node = head

    for (let i = 0; i < k; i++) {
        const next = node!.next
        node!.next = prev
        prev = node
        node = next
    }

    return prev
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n / k)，主要来自递归调用栈

如果按最坏情况粗略写，也可以理解成递归栈额外空间为 O(n) 级别。

这一解法的优缺点

优点：

思路很自然
更容易从“分治 / 递归”的角度理解

缺点：

不满足严格的 O(1) 额外空间要求
递归写法在链表题里有时不如迭代稳

两种解法对比

解法	时间复杂度	空间复杂度	特点
迭代分组翻转	`O(n)`	`O(1)`	最标准，面试最推荐
递归分组翻转	`O(n)`	`O(n / k)`	更好理解，但不是空间最优

如果你是为了面试，建议一定把第一种解法写熟。

手动模拟一遍迭代解法

以：

text

head = [1,2,3,4,5], k = 2

为例。

第 1 轮

当前链表：

text

dummy -> 1 -> 2 -> 3 -> 4 -> 5

找到这一组：

text

[1, 2]

翻转后：

text

dummy -> 2 -> 1 -> 3 -> 4 -> 5

此时：

groupPrev 移到 1

第 2 轮

当前待翻转部分：

text

3 -> 4 -> 5

找到这一组：

text

[3, 4]

翻转后：

text

dummy -> 2 -> 1 -> 4 -> 3 -> 5

此时：

groupPrev 移到 3

第 3 轮

剩下：

text

[5]

不足 k = 2 个，不翻，结束。

最终答案：

text

2 -> 1 -> 4 -> 3 -> 5

面试时最容易错的点

1. 最后一组不足 `k` 个时不能翻

这题和“整段链表翻转”最大的区别就在这里。

一定要先确认这一组是否有完整的 k 个节点。

2. 翻转时终止条件别写错

在迭代写法里，当前组翻转通常写成：

while (cur !== groupNext) {
    ...
}

因为我们只想翻这一组，不想把后面的节点也卷进去。

3. 翻完之后谁是新的尾巴

翻转前的组头，翻完后会变成组尾。

也就是：

groupPrev.next

在翻转前是组头，翻转后它会成为下一轮的 groupPrev。

4. 递归法不满足严格的 `O(1)` 空间

很多人会觉得“我没有开数组，所以是 O(1)”。

但递归调用栈本身也要算空间。

一句话总结

这题的本质是：

每次抓出一段长度为 k 的链表，把它原地翻转，再接回原链表。

想做面试标准解：用 迭代分组翻转
想先理解递归拆解：用 递归分组翻转

25. K 个一组翻转链表

题目描述

示例 1

示例 2

约束

进阶

核心思路

解法一：迭代分组翻转

思路拆解

这题需要记住的几个指针

一步一步写出算法

第一步：先准备虚拟头节点

第二步：找到当前组的第 k 个节点

第三步：记录下一组的起点

第四步：翻转当前这一组

第五步：重新接回链表

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：递归分组翻转

思路拆解

一步一步写出算法

第一步：先判断够不够 k 个节点

第二步：先递归处理后面的部分

第三步：翻转当前前 k 个节点

第四步：返回新的组头

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍迭代解法

第 1 轮

第 2 轮

第 3 轮

面试时最容易错的点

1. 最后一组不足 k 个时不能翻

2. 翻转时终止条件别写错

3. 翻完之后谁是新的尾巴

4. 递归法不满足严格的 O(1) 空间

一句话总结

推荐你最后记住的标准写法

第二步：找到当前组的第 `k` 个节点

第一步：先判断够不够 `k` 个节点

第三步：翻转当前前 `k` 个节点

1. 最后一组不足 `k` 个时不能翻

4. 递归法不满足严格的 `O(1)` 空间