511 lines
18 KiB
Markdown
511 lines
18 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "虚拟头节点", "迭代", "递归", "困难"]
|
||
create time: 2026-05-17 10:00
|
||
---
|
||
|
||
# 31-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 <= k <= n <= 5000`
|
||
- `0 <= Node.val <= 1000`
|
||
|
||
**进阶：** 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心洞察
|
||
> 这是一道**组合题**——它把两个经典操作叠加在了一起：**分组 + 反转**。分解来看：
|
||
> - 如果只有"反转链表"，那是 23 题（基础）
|
||
> - 如果只有"分组拼接"，那只需要追踪头尾即可
|
||
> - 现在要把两者结合起来，难点在于**每次反转一段后如何正确衔接回主链**
|
||
|
||
### 关键问题：如何定位一段的起止？
|
||
|
||
> [!warning] ⚠️ 最大陷阱
|
||
> 反转一个区间 `[a, b]` 时，反转完成后 a 会变成这段的**尾节点**，b 会变成**头节点**。如果你不提前保存 a.Next（即下一段的起点），反转完就找不到路了。
|
||
|
||
所以每组反转前，需要明确三个位置：
|
||
|
||
| 角色 | 含义 | 何时获取 |
|
||
|------|------|---------|
|
||
| **groupHead** | 当前这一组的第一个节点（反转后变成尾巴） | 进入本组时 |
|
||
| **groupTail** | 当前这一组的最后一个节点（反转后变成头部） | 遍历 k 步找到 |
|
||
| **nextGroup** | 下一组的起点 = groupTail.Next | 先存下来再反转 |
|
||
|
||
|
||
### 方法一：迭代法 ⭐（最优 — O(1) 空间）
|
||
|
||
用一个**虚拟头节点** `dummy` 统一边界处理，维护一个 `prev` 指针指向**已处理部分的尾节点**。每一轮做三件事：
|
||
|
||
1. **探路**：从 `prev.Next` 出发走 k 步，看是否有完整的 k 个节点
|
||
2. **反转**：如果有，反转这一段（利用第 23 题的单次反转模板）
|
||
3. **衔接**：将上一段的尾巴 `prev` 接到新头，再把旧头（现在变尾巴）连到下一段
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph Prepare["准备工作"]
|
||
D["dummy → head"] --> PREV["prev 初始指向 dummy"]
|
||
end
|
||
|
||
subgraph Phase1["阶段一：完整反转"]
|
||
P1["第 1 组: [1,2,3,4,5], k=2"] --> R1["反转 (1,2) → [2,1,4,3,5]\ndummy→2→1→4→3→5\nprev=1"]
|
||
R1 --> P2["第 2 组: [4,3,5], k=2"]
|
||
P2 --> R2["反转 (4,3) → [2,1,4,3,5]\nprev=3"]
|
||
R2 --> CheckFull{"剩余节点 ≥ k?\n[5], k=2 → 否"}
|
||
end
|
||
|
||
subgraph Phase2["阶段二：不足 k 个，跳过"]
|
||
CheckFull -- 否 --> SKIP["直接退出\n保留剩余 [5] ✅\ndummy→2→1→4→3→5"]
|
||
end
|
||
|
||
Prepare --> Phase1 --> Phase2
|
||
|
||
style Prepare fill:#bbf,stroke:#333
|
||
style R1 fill:#f9d,stroke:#333
|
||
style R2 fill:#f9d,stroke:#333
|
||
style SKIP fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
**逐步展开（以 `head = [1,2,3,4,5], k = 2` 为例）：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Init["① 初始状态"]
|
||
D1["dummy"] --> N1["1"]
|
||
N1 --> N2["2"]
|
||
N2 --> N3["3"]
|
||
N3 --> N4["4"]
|
||
N4 --> N5["5"]
|
||
PREV1["prev=dummy"]
|
||
end
|
||
|
||
subgraph Probe1["② 探路: 从 prev.Next=1 走 k=2 步\n找到 groupTail=2"]
|
||
P1["1→2 共 2 个节点 ✅ 满足 k"]
|
||
end
|
||
|
||
subgraph Reverse1["③ 反转 (1,2): 先保存 nextGroup=3\n反转后: 2→1, 然后 1.Next=3"]
|
||
REV1["2→1→3→4→5"]
|
||
end
|
||
|
||
subgraph Connect1["④ 衔接: prev.Next=2(新头), prev=1(旧头)\ndummy→2→1→3→4→5"]
|
||
CONN1["dummy→2→1→3→4→5\nprev=1"]
|
||
end
|
||
|
||
subgraph Probe2["⑤ 探路: 从 prev.Next=3 走 k=2 步\n找到 groupTail=4"]
|
||
P2["3→4 共 2 个节点 ✅ 满足 k"]
|
||
end
|
||
|
||
subgraph Reverse2["⑥ 反转 (3,4): 先保存 nextGroup=5\n反转后: 4→3, 然后 3.Next=5"]
|
||
REV2["dummy→2→1→4→3→5"]
|
||
end
|
||
|
||
subgraph Connect2["⑦ 衔接: prev.Next=4(新头), prev=3"]
|
||
CONN2["dummy→2→1→4→3→5\nprev=3"]
|
||
end
|
||
|
||
subgraph Done["⑧ 探路: 从 prev.Next=5 走 k=2 步\n只剩 1 个节点 < k ❌ 退出"]
|
||
DONE["dummy→2→1→4→3→5 ✅"]
|
||
end
|
||
|
||
Init --> Probe1 --> Reverse1 --> Connect1 --> Probe2 --> Reverse2 --> Connect2 --> Done
|
||
|
||
classDef initStyle fill:#bbf,stroke:#333
|
||
classDef probeStyle fill:#ffd700,stroke:#333
|
||
classDef reverseStyle fill:#f9d,stroke:#333
|
||
classDef connectStyle fill:#9df,stroke:#333
|
||
classDef doneStyle fill:#d4edda,stroke:#28a
|
||
class Init initStyle
|
||
class Probe1,P2 probeStyle
|
||
class Reverse1,Reverse2 reverseStyle
|
||
class Connect1,Connect2 connectStyle
|
||
class Done,DONE doneStyle
|
||
```
|
||
|
||
> [!question] 💡 引导思考：为什么 prev 前进到旧头（groupHead）？
|
||
> 反转完成后，旧的 groupHead 变成了这段的**末尾节点**，它的 Next 已经指向下一组的开头。所以 `prev = groupHead` 恰好让它在下一轮可以访问 `prev.Next`（下一组的第一个节点）。这和「两两交换」的思路完全一致——只不过这里每组有 k 个节点而不是 2 个。
|
||
|
||
**代码流程：**
|
||
|
||
```
|
||
dummy = &ListNode{Next: head}
|
||
prev = dummy
|
||
|
||
for {
|
||
// 步骤 1：找第 k 个节点
|
||
kth = prev
|
||
for i = 1; i <= k; i++ {
|
||
kth = kth.Next
|
||
if kth == nil { // 不足 k 个节点
|
||
return dummy.Next // 剩余部分保持原序，直接退出
|
||
}
|
||
}
|
||
|
||
// 步骤 2：记录两组之间的连接点
|
||
nextGroup = kth.Next // 下一组起点
|
||
groupHead = prev.Next // 当前组起点（反转后变末尾）
|
||
|
||
// 步骤 3：切断与下组的联系，然后反转 [prev.Next, kth]
|
||
kth.Next = nil
|
||
revHead := reverseList(prev.Next)
|
||
|
||
// 步骤 4：重新拼接
|
||
prev.Next = revHead // 上段尾巴 → 新头
|
||
groupHead.Next = nextGroup // 旧头（现尾巴）→ 下一段
|
||
|
||
// 步骤 5：prev 走到已处理段的末尾，准备下一轮
|
||
prev = groupHead
|
||
}
|
||
```
|
||
|
||
其中 `reverseList(head)` 就是 23 题的单链表反转（头插法或三指针法）：
|
||
|
||
```
|
||
func reverseList(head *ListNode) *ListNode {
|
||
var prev *ListNode
|
||
curr := head
|
||
for curr != nil {
|
||
nextTemp := curr.Next
|
||
curr.Next = prev
|
||
prev = curr
|
||
curr = nextTemp
|
||
}
|
||
return prev
|
||
}
|
||
```
|
||
|
||
> [!info] 🧠 串联的"断链再续"策略
|
||
> 核心技巧是：**先在 kth.Next 处断开（`kth.Next = nil`），形成一个独立的子链表交给 reverseList，反转完再把两头接回主链**。这样做的好处是——反转函数不需要感知主链的存在，保持了函数的纯度和复用性。
|
||
|
||
**时间复杂度：O(n)** — 每个节点被 visit 常数次（一次探路、一次反转）
|
||
**空间复杂度：O(1)** — 只用了有限个指针变量
|
||
|
||
---
|
||
|
||
### 方法二：递归法
|
||
|
||
递归的核心思想更简洁：**假设第 2 组及以后的部分已经处理好了，我只管搞定第一组，然后把它们串起来。**
|
||
|
||
**递归框架：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
S1["① 从 head 开始遍历 k 步\n确认剩余节点 ≥ k?"] --> S2["② 是: 反转第一组\ntail.next = reverseKGroup(nextGroup, k)\nreturn newHead"] --> S3["③ 否: 剩余不足 k 个\n直接返回 head, 不做任何改动"]
|
||
|
||
style S1 fill:#bbf,stroke:#333
|
||
style S2 fill:#f9d,stroke:#333
|
||
style S3 fill:#fff4e6,stroke:#f90
|
||
```
|
||
|
||
**以 `head = [1,2,3,4,5], k = 2` 为例：**
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph Explore["递：一路往下探，同时数节点"]
|
||
E1["countNodes(1) = 5 ≥ 2\n继续"] --> E2["countNodes(3) = 3 ≥ 2\n继续"] --> E3["countNodes(5) = 1 < 2\n❌ 停止"]
|
||
end
|
||
|
||
subgraph Build["归：一层层往回构造"]
|
||
B1["L2: 反转(5), 只剩1个<k → 返回 5\nreverseKGroup(5)=5"] --> B2["L1: 反转(3,4)→4→3\n4.next = L2返回值(5)\n结果: 4→3→5\n返回 4"]
|
||
B2 --> B3["L0: 反转(1,2)→2→1\n2.next = L1返回值(4)\n结果: 2→1→4→3→5\n返回 2 ✅"]
|
||
end
|
||
|
||
Explore --> Build
|
||
|
||
style Explore fill:#eee,stroke:#999
|
||
style B1 fill:#fff4e6,stroke:#f90
|
||
style B2 fill:#bbf,stroke:#333
|
||
style B3 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
逐步展开：
|
||
|
||
| 递归层级 | 传入 head | 剩余节点数 | action | 返回值 |
|
||
|---------|-----------|----------|--------|--------|
|
||
| L0 | `1→2→3→4→5` | 5 ≥ 2 | 反转 (1,2)，next = L1 | `2→1→...` |
|
||
| L1 | `3→4→5` | 3 ≥ 2 | 反转 (3,4)，next = L2 | `4→3→...` |
|
||
| L2 | `5` | 1 < 2 | 不足 k，直接返回 | `5` |
|
||
|
||
**关键连接点：**
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
AfterL2["L2 返回: 5（未变化）"] --> Link1["L1: tail=3, 3.Next = 5\n得到 4→3→5"]
|
||
Link1 --> Link0["L0: tail=1, 1.Next = 4\n得到 2→1→4→3→5 ✅"]
|
||
|
||
style AfterL2 fill:#eee,stroke:#999
|
||
style Link1 fill:#bbf,stroke:#333
|
||
style Link0 fill:#d4edda,stroke:#28a
|
||
```
|
||
|
||
> [!warning] ⚠️ 不要手动断链！
|
||
> 递归法和迭代法不同：**不应该设置 `kth.Next = nil`**。递归的反转需要在子链表上进行，但我们希望反转后每个节点仍然能顺着 Next 找到同一组内的后继（这样才能用 `tail.Next = reverseKGroup(...)` 自然衔接）。具体做法是在反转之前保存好每对相邻节点的关系，详见下方代码。
|
||
|
||
**时间复杂度：O(n × n/k) = O(n²/k)** — 每层递归调用 `countNodes` 遍历剩余节点
|
||
**空间复杂度：O(n/k)** — 递归栈深度为 n/k
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 迭代法伪代码
|
||
|
||
```
|
||
func reverseKGroup(head, k):
|
||
dummy = &ListNode{Next: head}
|
||
prev = dummy
|
||
|
||
for {
|
||
// 探路：找第 k 个节点
|
||
kth = prev
|
||
for i = 1; i <= k; i++ {
|
||
kth = kth.Next
|
||
if kth == nil:
|
||
return dummy.Next // 不足 k 个，退出
|
||
|
||
// 记录边界
|
||
nextGroup = kth.Next // 下一组起点
|
||
groupHead = prev.Next // 当前组起点
|
||
|
||
// 切断、反转、接回
|
||
kth.Next = nil
|
||
newHead = reverseList(prev.Next)
|
||
|
||
prev.Next = newHead // 上段接新头
|
||
groupHead.Next = nextGroup // 旧头（现尾）接下一段
|
||
|
||
// 移动 prev
|
||
prev = groupHead
|
||
}
|
||
|
||
func reverseList(head):
|
||
prev = nil
|
||
curr = head
|
||
while curr != nil:
|
||
nextTemp = curr.Next
|
||
curr.Next = prev
|
||
prev = curr
|
||
curr = nextTemp
|
||
return prev
|
||
```
|
||
|
||
### 递归法伪代码
|
||
|
||
```
|
||
func reverseKGroup(head, k):
|
||
// 第一步：检查是否有足够节点
|
||
curr = head
|
||
for i = 0; i < k && curr != nil; i++:
|
||
curr = curr.Next
|
||
|
||
if curr == nil:
|
||
return head // 不足 k 个，保持原序
|
||
|
||
// 第二步：反转前 k 个节点（注意不全断链）
|
||
prev = nil
|
||
curr = head
|
||
for i = 0; i < k; i++:
|
||
nextTemp = curr.Next
|
||
curr.Next = prev // 反向指
|
||
prev = curr
|
||
curr = nextTemp
|
||
|
||
// 第三步：head 现在是这一组的末尾，接到递归结果
|
||
// 此时 head.Next 还没被破坏（curr = head.Next 在先）
|
||
head.Next = reverseKGroup(curr, k)
|
||
|
||
return prev // prev 是反转后的新头
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 "断链再续"模式（迭代法精髓）
|
||
> 碰到需要原地修改链表中某一段的场景，可以先在这段的**两端分别断开**，得到一个独立子链表，做完操作后再把首尾接回主链。这个模式反复出现在：
|
||
> - 本题：按 k 组切分
|
||
> - 反转链表的一部分（LeetCode 92）
|
||
> - 旋转链表（LeetCode 61）
|
||
|
||
> [!tip] 🔑 递归的"贪心假设"
|
||
> 递归解法的核心自信来自一句假设：**"后面的部分交给我，一定能处理好。"** 你只需要验证两件事：① 这一层自己做得对不对；② 传给下一层的参数是不是正确的起始位置。不用想全貌。
|
||
|
||
> [!warning] ⚠️ 常见错误 1：忘记处理不足 k 个的情况
|
||
> 当最后剩余节点少于 k 个时，题目要求保持原序不变。如果在探路时发现 `kth == nil` 没有及时 return，后面 `kth.Next = nil` 会把有效节点裁掉，导致链表丢失后半段。
|
||
|
||
> [!warning] ⚠️ 常见错误 2：递归中错误断链
|
||
> 递归解法里千万不要设 `kth.Next = nil`。因为递归依靠 `head.Next = reverseKGroup(curr, k)` 来拼接，如果中间断了，递归回来的结果就连不上了。
|
||
|
||
> [!warning] ⚠️ 常见错误 3：迭代中 prev 走错位置
|
||
> 每组处理完后，prev 必须走到**旧头节点**（即这一组反转前的第一个节点，现在是最后一个），因为只有它才有正确的 Next 指向下一组。很多同学在 prev = groupHead 这一步会混淆新旧关系。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 维度 | 迭代法 ⭐ | 递归法 |
|
||
|------|---------|--------|
|
||
| 时间复杂度 | O(n) | O(n²/k) |
|
||
| 空间复杂度 | O(1) | O(n/k)（递归栈） |
|
||
| 代码行数 | 循环体约 15 行 | 核心逻辑约 15 行 |
|
||
| 直观程度 | 中等（需理解"断链再续"） | 较高（"搞一组，接尾巴"） |
|
||
| 面试推荐 | ⭐⭐⭐ 首选 | ⭐⭐ 可作为辅助展示 |
|
||
| 适用场景 | O(1) 空间约束时的唯一解 | 教学和理解分组思想 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - 这是链表分组操作的**终极题型**，它建立在所有前置链表题目的基础之上：
|
||
> - [23-反转链表](./23-反转链表.md) — 单次反转是基本操作
|
||
> - [30-两两交换链表中的节点](./30-两两交换链表中的节点.md) — K=2 的特例
|
||
> - [29-删除链表的倒数第 N 个结点](./29-删除链表的倒数第 N 个结点.md) — 快慢指针的距离控制
|
||
> - 同系列的进阶题目还有：
|
||
> - [25-K 个一组翻转链表](./) — 本题本身
|
||
> - [92-反转链表 II](https://leetcode.com/problems/reverse-linked-list-ii/) — 反转链表中的一段 [left, right]
|
||
> - [24-两两交换链表中的节点](./23-反转链表.md) — 特殊情况 K=2
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 迭代法（虚拟头节点 + 断链再续）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
// reverseList 反转一个单链表，返回新头节点
|
||
// 这是 23 题的标准解法——三指针法（头插法的变种）
|
||
func reverseList(head *ListNode) *ListNode {
|
||
var prev *ListNode // 前驱，初始为空
|
||
curr := head // 当前节点
|
||
for curr != nil {
|
||
nextTemp := curr.Next // 先保存下一个节点，避免断链后丢失
|
||
curr.Next = prev // 反向指向前驱
|
||
prev = curr // prev 前进一步
|
||
curr = nextTemp // curr 前进一步
|
||
}
|
||
return prev // prev 最终停在原链表的尾节点，即新头
|
||
}
|
||
|
||
func reverseKGroup(head *ListNode, k int) *ListNode {
|
||
// 虚拟头节点：消除"第一组前面没有 prev"的边界情况
|
||
dummy := &ListNode{Next: head}
|
||
prev := dummy // prev 始终指向已处理部分的尾节点
|
||
|
||
for {
|
||
// 步骤 1：探路——从 prev.Next 出发，向前走 k 步
|
||
kth := prev
|
||
for i := 1; i <= k; i++ {
|
||
kth = kth.Next
|
||
if kth == nil {
|
||
// 不足 k 个节点，剩余部分保持原序，直接返回
|
||
return dummy.Next
|
||
}
|
||
}
|
||
|
||
// 步骤 2：记录关键位置
|
||
groupHead := prev.Next // 当前组的第一个节点（反转后变末尾）
|
||
nextGroup := kth.Next // 下一组的起点
|
||
|
||
// 步骤 3：在 kth 处"断链"，形成独立子链表
|
||
kth.Next = nil
|
||
|
||
// 步骤 4：反转这段子链表，拿到新头
|
||
newHead := reverseList(groupHead)
|
||
|
||
// 步骤 5："接回"主链
|
||
prev.Next = newHead // 上一段的尾 → 当前组的新头
|
||
groupHead.Next = nextGroup // 当前组的旧头（现尾）→ 下一段
|
||
|
||
// 步骤 6：prev 前进到已处理段的末尾，准备下一轮
|
||
prev = groupHead
|
||
}
|
||
}
|
||
```
|
||
|
||
### 递归法
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func reverseKGroup(head *ListNode, k int) *ListNode {
|
||
// 第一步：检查是否有至少 k 个节点
|
||
cur := head
|
||
for i := 0; i < k && cur != nil; i++ {
|
||
cur = cur.Next
|
||
}
|
||
if cur == nil {
|
||
// 不足 k 个节点，保持原序不变
|
||
return head
|
||
}
|
||
|
||
// 第二步：反转前 k 个节点（注意不全断链）
|
||
var prev *ListNode
|
||
cur = head
|
||
for i := 0; i < k; i++ {
|
||
nextTemp := cur.Next // 保存下一个节点
|
||
cur.Next = prev // 反向指
|
||
prev = cur // prev 前进一步
|
||
cur = nextTemp // cur 前进一步
|
||
}
|
||
|
||
// 第三步：head 是这一组反转前的第一个节点，反转后变成了末尾
|
||
// 把它接到递归处理的后半段
|
||
head.Next = reverseKGroup(cur, k)
|
||
|
||
// prev 是反转后的新头
|
||
return prev
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 25 题，通过率约 50%+，属于硬实力区分题。面试官选它的目的很明确——考察候选人对链表操作的综合掌控力：能否在多个反转片段之间精准拼接、能否处理边界条件而不依赖特殊判断。迭代法是面试的首选答案，因为它同时满足 O(1) 空间和清晰的线性逻辑。递归法则展示了你对"问题分解"的理解深度。建议掌握以下三点作为面试亮点：① 用 dummy 节点统一所有边界；② 用"断链再续"保持函数纯净度；③ 能说清楚每一步的不变量是什么。
|
||
>
|
||
> > [!TIP] 💬 面试加分话术
|
||
> > "这道题本质上是把 n/k 个子问题（每个子问题是 O(k) 的单链表反转）串联起来。递归的自然写法会导致 O(n²/k) 的复杂度，因为每层递归都要重数节点；但如果预先把整条链扫一遍、收集所有分组头尾，就能降到 O(n)。不过在实际面试中，简洁的递归版本通常已经够用——关键是你能清晰解释每一步的连接关系。"
|