---
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)。不过在实际面试中，简洁的递归版本通常已经够用——关键是你能清晰解释每一步的连接关系。"