705 lines
20 KiB
Markdown
705 lines
20 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "分治", "归并排序", "递归", "中等"]
|
||
create time: 2026-05-18 14:30
|
||
---
|
||
|
||
# 33-排序链表
|
||
|
||
## 题面
|
||
|
||
给你链表的头结点 `head`，请将其按 **升序** 排列并返回排序后的链表。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [4,2,1,3]
|
||
输出：[1,2,3,4]
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = [-1,5,3,4,0]
|
||
输出：[-1,0,3,4,5]
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：head = []
|
||
输出：[]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中节点的数目在范围 `[0, 5 * 10^4]` 内
|
||
- `-10^5 <= Node.val <= 10^5`
|
||
- **进阶：** 你可以在 `O(n log n)` 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 引导思考
|
||
> 对数组排序，你最熟悉的是什么算法？快速排序、归并排序、堆排序——它们的平均时间复杂度都是 O(n log n)。但有一个关键差异：**数组支持随机访问**，可以通过下标 O(1) 拿到中间元素；而**链表只能顺序遍历**。这意味着基于二分查找思想的算法在链表上会遇到困难。
|
||
|
||
> [!warning] ⚠️ 为什么这些常见排序算法不适合链表？
|
||
|
||
| 排序算法 | 链表上的问题 |
|
||
|---------|------------|
|
||
| **快速排序** | 分区时需要双向遍历，链表只支持单向移动；且最坏情况 O(n²)，不稳定 |
|
||
| **堆排序** | 堆的底层是数组，需要通过下标访问子节点，链表无法做到 O(1) |
|
||
| **插入排序** | ✅ 可行，但时间复杂度 O(n²)，不满足进阶要求 |
|
||
| **归并排序** | ✅ 天然适合链表——只需顺序遍历找中点 + 指针重连，不需要随机访问 |
|
||
|
||
> [!info] 🧠 为什么归并排序是链表的最优选择？
|
||
> - **数组归并**需要额外 O(n) 空间存临时数组
|
||
> - **链表归并**只需要修改指针，可以做到 O(1) 额外空间（递归版本因调用栈为 O(log n)，迭代版本可达真正的 O(1)）
|
||
> - 找中点可以用快慢指针一次遍历完成，不需要随机访问
|
||
|
||
### 方法一：自顶向下归并排序（递归）⭐（推荐，面试首选）
|
||
|
||
归并排序的核心三步：**分 → 治 → 合**。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph DIVIDE["① 分：递归拆分"]
|
||
A["4→2→1→3"] -->|"找中点"| B["4→2 和 1→3"]
|
||
B -->|"继续分"| C["4, 2, 1, 3"]
|
||
end
|
||
|
||
subgraph CONQUER["② 治：单节点即有序"]
|
||
D["4 ✓ 2 ✓\n1 ✓ 3 ✓"]
|
||
end
|
||
|
||
subgraph MERGE["③ 合：逐层合并"]
|
||
E["2→4 和 1→3"] --> F["1→2→3→4 ✓"]
|
||
end
|
||
|
||
A --> C --> D --> E --> F
|
||
style F fill:#4c4,stroke:#333,stroke-width:2px,color:white
|
||
```
|
||
|
||
#### 第一步：用快慢指针找中点
|
||
|
||
> [!question] 💡 回顾一下：如何只用一趟遍历找到链表的"中间位置"？
|
||
|
||
使用经典的快慢指针法：`fast` 每次走两步，`slow` 每次走一步。当 `fast` 到达末尾时，`slow` 恰好位于中点。
|
||
|
||
```go
|
||
slow, fast := head, head.Next
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
}
|
||
```
|
||
|
||
此时 `slow` 指向**左半段的最后一个节点**（偶数长度时偏左），将链表从中断开：
|
||
|
||
```go
|
||
mid := slow.Next // 右半段的起点
|
||
slow.Next = nil // 断开左半段 ← 关键！必须切断，否则会死循环
|
||
```
|
||
|
||
以 `4→2→1→3` 为例：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph "断开前"
|
||
A["4→2→1→3"]
|
||
end
|
||
|
||
subgraph "slow定位到节点2\nfast到达nil"
|
||
B["4→2 ★"] -.断开.-> C["1→3 ★"]
|
||
end
|
||
|
||
subgraph "结果：两个独立子链表"
|
||
L["left: 4→2→nil"]
|
||
R["right: 1→3→nil"]
|
||
end
|
||
|
||
B --> L
|
||
B --> R
|
||
style L fill:#d4edda,stroke:#28a
|
||
style R fill:#cce5ff,stroke:#28a
|
||
```
|
||
|
||
> [!tip] 🔑 为什么要执行 `slow.Next = nil`？
|
||
> 如果不切断，左右两半仍然相连，递归调用 `sortList(slow)` 时会无限深入到底，导致栈溢出。这是本题最容易忽略的细节！
|
||
|
||
#### 第二步：合并两个有序链表
|
||
|
||
这一步直接复用 [27-合并两个有序链表](./27-合并两个有序链表.md) 中的迭代合并逻辑。
|
||
|
||
```go
|
||
func merge(l1, l2 *ListNode) *ListNode {
|
||
dummy := &ListNode{}
|
||
tail := dummy
|
||
|
||
for l1 != nil && l2 != nil {
|
||
if l1.Val <= l2.Val {
|
||
tail.Next = l1
|
||
l1 = l1.Next
|
||
} else {
|
||
tail.Next = l2
|
||
l2 = l2.Next
|
||
}
|
||
tail = tail.Next
|
||
}
|
||
|
||
if l1 != nil {
|
||
tail.Next = l1
|
||
} else {
|
||
tail.Next = l2
|
||
}
|
||
|
||
return dummy.Next
|
||
}
|
||
```
|
||
|
||
#### 第三步：完整递归框架
|
||
|
||
```go
|
||
func sortList(head *ListNode) *ListNode {
|
||
// 基准情况：空链表或单节点，本身就是有序的
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// ① 找中点并断开
|
||
slow, fast := head, head.Next
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
}
|
||
mid := slow.Next
|
||
slow.Next = nil // 切断，分左右两半
|
||
|
||
// ② 递归排序左右两半
|
||
left := sortList(head)
|
||
right := sortList(mid)
|
||
|
||
// ③ 合并结果
|
||
return merge(left, right)
|
||
}
|
||
```
|
||
|
||
以 `[4,2,1,3]` 为例的完整执行树：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph "顶层 sortList(4→2→1→3)"
|
||
SPLIT["拆分: 4→2 | 1→3"]
|
||
end
|
||
|
||
subgraph "左半边 sortList(4→2)"
|
||
LSPLIT["拆分: 4 | 2"]
|
||
LMERGE["合并: 2→4 ✓"]
|
||
end
|
||
|
||
subgraph "右半边 sortList(1→3)"
|
||
RSPLIT["拆分: 1 | 3"]
|
||
RMERGE["合并: 1→3 ✓"]
|
||
end
|
||
|
||
subgraph "顶层合并"
|
||
FINAL["合并 2→4 和 1→3\n→ 1→2→3→4 ✓"]
|
||
end
|
||
|
||
SPLIT --> LSPLIT --> LMERGE
|
||
SPLIT --> RSPLIT --> RMERGE
|
||
LMERGE --> FINAL
|
||
RMERGE --> FINAL
|
||
style FINAL fill:#4c4,color:white,stroke:#333,stroke-width:2px
|
||
```
|
||
|
||
逐步展开 `[4,2,1,3]` 的执行过程：
|
||
|
||
| 阶段 | 操作 | 状态 |
|
||
|------|------|------|
|
||
| sortList([4,2,1,3]) | 拆分为 [4,2] 和 [1,3] | — |
|
||
| sortList([4,2]) | 拆分为 [4] 和 [2] | 两半均为单节点，直接返回 |
|
||
| merge([4], [2]) | 2 < 4，先接 2 再接 4 | 返回 2→4 |
|
||
| sortList([1,3]) | 拆分为 [1] 和 [3] | 两半均为单节点，直接返回 |
|
||
| merge([1], [3]) | 1 < 3，先接 1 再接 3 | 返回 1→3 |
|
||
| merge([2,4], [1,3]) | 逐一对比合并 | 返回 **1→2→3→4** ✅ |
|
||
|
||
**时间复杂度：O(n log n)** — 深度为 log n 层，每层的合并总代价为 O(n)。
|
||
**空间复杂度：O(log n)** — 递归调用栈的深度等于树的深度。
|
||
|
||
> [!note] 🤔 进阶问题的答案
|
||
> 题目要求"常数级空间复杂度"，递归版本的 O(log n) 来自调用栈。严格来说不满足"常数量级"。但在面试中这个版本已经完全够用，因为：① 代码简洁清晰；② log n 在实际规模下极小（n=5×10⁴ 时 log₂n ≈ 16）。如果追求理论最优的 O(1) 空间，见下方迭代版本。
|
||
|
||
---
|
||
|
||
### 方法二：自底向上归并排序（迭代）🏆（严格 O(1) 空间）
|
||
|
||
> [!question] 💡 如何消除递归调用栈的开销？
|
||
> 观察递归版的调用树——它是一棵满二叉树，从叶子往根方向一层层合并。如果我们**放弃递归**，改为从最小的子区间（长度为 1）开始，逐级扩大子区间长度（1→2→4→8...），就能用迭代模拟相同的过程。
|
||
|
||
#### 核心思想
|
||
|
||
从长度为 `1` 的子链表开始，逐层合并，直到子链表长度 `>= n`：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
STEP1["gap=1\n4|2|1|3"] --> STEP2["gap=2\n2→4 | 1→3"]
|
||
STEP2 --> STEP3["gap=4\n1→2→3→4 ✓"]
|
||
|
||
style STEP1 fill:#e8f5e9,stroke:#28a
|
||
style STEP2 fill:#fff4e6,stroke:#f90
|
||
style STEP3 fill:#4c4,color:white,stroke:#333
|
||
```
|
||
|
||
每一层的步骤相同：从头到尾扫描整个链表，每次取两段长度为 `gap` 的子链表进行合并。
|
||
|
||
#### 关键难点：如何分段
|
||
|
||
给定当前 `gap`，需要找出四个关键点：
|
||
|
||
```
|
||
[BH]───第1段(gap个)───[H]───第2段(gap个)───[TN]──────────剩余───────────→
|
||
BH H TN
|
||
|
||
BH = Before Head 上一段尾部（下一段的头部）
|
||
H = Head 当前第1段的头部
|
||
TN = Tail Next 第2段尾部的下一个节点（用于重新拼接）
|
||
```
|
||
|
||
| 变量 | 含义 | 如何计算 |
|
||
|------|------|---------|
|
||
| `h` | 第 1 段头部 | 从 `split(bh, gap)` 获得 |
|
||
| `t` | 第 1 段尾部 | 同上，同时返回尾部 |
|
||
| `h2` | 第 2 段头部 | `split(t, gap)` 获得 |
|
||
| `tn` | 拼接点 | `split(t2, gap)` 获得第 2 段尾部后，取其 `Next` |
|
||
|
||
其中辅助函数 `split(head, gap)` 的作用是：从 `head` 出发往后走 `gap` 步，将第 `gap` 个节点的 `Next` 置为 `nil`（切断），并返回 `(head, tail)`。
|
||
|
||
#### 完整伪代码
|
||
|
||
```
|
||
n = 计算链表总长度
|
||
|
||
gap = 1
|
||
while gap < n {
|
||
bh = nil // 虚拟头节点的前驱
|
||
cur = dummy // dummy 挂在原链表头部前方
|
||
|
||
while cur != nil {
|
||
h, t = split(cur.Next, gap) // 取出第 1 段
|
||
h2, t2 = split(t.Next, gap) // 取出第 2 段
|
||
|
||
tn = t2.Next // 保存下一段的起点
|
||
|
||
t.Next = nil // 断开第 1 段尾部
|
||
t2.Next = nil // 断开第 2 段尾部
|
||
|
||
merged = merge(h, h2) // 合并两段
|
||
|
||
bh.Next = merged // 接到前一段后面
|
||
bh = t2 // 更新前驱
|
||
cur = tn // 跳到下一组
|
||
}
|
||
|
||
gap *= 2 // 翻倍，进入下一层
|
||
}
|
||
|
||
return dummy.Next
|
||
```
|
||
|
||
#### 完整 Go 代码
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func sortList(head *ListNode) *ListNode {
|
||
// 边界检查
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// ① 计算链表长度
|
||
n := 0
|
||
for node := head; node != nil; node = node.Next {
|
||
n++
|
||
}
|
||
|
||
// 虚拟头节点：简化边界处理
|
||
dummy := &ListNode{Next: head}
|
||
|
||
// ② 自底向上逐层合并：gap = 1, 2, 4, 8, ...
|
||
for gap := 1; gap < n; gap *= 2 {
|
||
prev, cur := dummy, dummy
|
||
|
||
// ③ 在当前层从头到尾扫描，每次取两段长度为 gap 的子链表合并
|
||
for cur.Next != nil {
|
||
h1, t1 := split(cur.Next, gap) // 第 1 段
|
||
h2, t2 := split(t1.Next, gap) // 第 2 段
|
||
next := t2.Next // 保存下一组的起点
|
||
|
||
t1.Next, t2.Next = nil, nil // 断开分段
|
||
merged := merge(h1, h2) // 合并两段
|
||
|
||
prev.Next = merged // 接上前一段
|
||
prev = tailOf(merged) // 更新 prev 到合并后链表的尾部
|
||
cur = next // 跳到下一组
|
||
}
|
||
}
|
||
|
||
return dummy.Next
|
||
}
|
||
|
||
// split 从 head 出发截取 length 个节点
|
||
// 返回 (头部, 尾部)，并将尾部 Next 保持原样（由调用者负责断开）
|
||
func split(head *ListNode, length int) (*ListNode, *ListNode) {
|
||
if head == nil {
|
||
return nil, nil
|
||
}
|
||
h := head
|
||
t := head
|
||
for i := 1; i < length && t.Next != nil; i++ {
|
||
t = t.Next
|
||
}
|
||
next := t.Next // 记录切断后的下一段起点
|
||
t.Next = nil // 切断
|
||
return h, next // 注意：这里返回的是切断后的下一段作为"尾部"的代理
|
||
}
|
||
```
|
||
|
||
> [!warning] ⚠️ 迭代版实现技巧
|
||
> 上述伪代码中 `split` 的签名做了一点调整以适应实际代码。下面给出可直接提交的完整版本，包含精妙的实现细节。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 递归版伪代码
|
||
|
||
```
|
||
func sortList(head):
|
||
// 基准情况
|
||
if head == nil or head.Next == nil:
|
||
return head
|
||
|
||
// ① 找中点并断开
|
||
slow, fast = head, head.Next
|
||
while fast != nil and fast.Next != nil:
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
|
||
mid = slow.Next
|
||
slow.Next = nil // ← 关键！切断避免死循环
|
||
|
||
// ② 递归排序
|
||
left = sortList(head)
|
||
right = sortList(mid)
|
||
|
||
// ③ 合并
|
||
return merge(left, right)
|
||
```
|
||
|
||
### 迭代版伪代码
|
||
|
||
```
|
||
n = 计算链表长度
|
||
dummy = &ListNode{Next: head}
|
||
|
||
for gap = 1; gap < n; gap *= 2:
|
||
prev = dummy
|
||
cur = dummy
|
||
|
||
while cur.Next != nil:
|
||
h1, t1 = 取 gap 个节点
|
||
h2, t2 = 再取 gap 个节点
|
||
nextGroup = t2.Next
|
||
|
||
断开 t1.Next, t2.Next
|
||
merged = merge(h1, h2)
|
||
|
||
prev.Next = merged
|
||
prev = merged的尾部
|
||
cur = nextGroup
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 归并排序的通用模板（适用于任何可顺序遍历的结构）
|
||
>
|
||
> ```
|
||
> 递归版：
|
||
> func Sort(head):
|
||
> if 太短: return head
|
||
> mid = FindMiddle(head)
|
||
> left = Sort(head)
|
||
> right = Sort(mid)
|
||
> return Merge(left, right)
|
||
>
|
||
> 迭代版：
|
||
> for gap = 1; gap < N; gap *= 2:
|
||
> 遍历整条链，每次取两段 gap 长度的子序列合并
|
||
> ```
|
||
>
|
||
> 这套模板可以推广到：二叉树 flattening（转成有序链表）、有序流合并等场景。
|
||
|
||
> [!tip] 🔑 为什么链表排序不用快排？
|
||
> 快排的核心优势是原地分区和缓存局部性——这两个优势在链表上都消失了：
|
||
> - 分区时需要前后双向移动指针，链表只能单向遍历，效率打折
|
||
> - 链表节点分散在堆内存中，无缓存友好性
|
||
> - 快排最坏 O(n²)（虽然可以用三数取中等 trick 缓解），而归并稳定保证 O(n log n)
|
||
>
|
||
> **结论：链表排序的标准答案就是归并排序。**
|
||
|
||
> [!note] 🔑 找中点的三种初始化方式对比
|
||
|
||
| 初始化 | slow 最终位置（偶数 n）| 特点 |
|
||
|--------|----------------------|------|
|
||
| `slow=head, fast=head` | 第 n/2 个 | 左半段少一个节点 |
|
||
| `slow=head, fast=head.Next` | 第 n/2 个 | 标准写法，推荐 ✅ |
|
||
| `slow=head, fast=head.Next.Next` | 第 n/2+1 个 | 左半段多一个节点 |
|
||
|
||
对于归并排序而言，选哪种都可以，只要保证左右分配合理即可。本文采用 `fast=head.Next`。
|
||
|
||
> [!tip] 🔑 合并时为什么要复制节点值而不是创建新节点？
|
||
> 在 `merge` 过程中，我们直接重用了原有节点的引用（`tail.Next = l1/l2`），没有创建新节点。这保证了空间复杂度为 O(1)。如果每次都创建新节点，空间会退化到 O(n)。
|
||
|
||
> [!info] 📊 两种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|
||
|------|-----------|-----------|------|------|
|
||
| **递归归并 ⭐** | **O(n log n)** | **O(log n)** | 代码简洁、易理解、面试首选 | 调用栈占用 O(log n) |
|
||
| **迭代归并 🏆** | **O(n log n)** | **O(1)** | 严格满足常数空间 | 代码繁琐、指针操作复杂 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [27-合并两个有序链表](./27-合并两个有序链表.md) — 归并排序的合并步骤直接使用此题的解法
|
||
> - [[148-排序链表]] — LeetCode 同题，可用相同解法
|
||
> - [[23-合并K个升序链表]] — 进阶扩展：用优先队列优化 K 路合并
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 方法一：自顶向下归并排序（递归）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func sortList(head *ListNode) *ListNode {
|
||
// 基准情况：空链表或只有一个节点，本身就是有序的
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// ① 快慢指针找中点 —— fast 从 head.Next 开始
|
||
slow, fast := head, head.Next
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next
|
||
fast = fast.Next.Next
|
||
}
|
||
|
||
// ② 从中点断开，分成两个独立的子链表
|
||
mid := slow.Next
|
||
slow.Next = nil // ← 关键！切断连接，否则递归不会终止
|
||
|
||
// ③ 递归排序左右两部分
|
||
left := sortList(head)
|
||
right := sortList(mid)
|
||
|
||
// ④ 合并两个有序子链表
|
||
return merge(left, right)
|
||
}
|
||
|
||
// merge 合并两个有序链表，返回新的头节点
|
||
// 复用 27-合并两个有序链表的迭代实现
|
||
func merge(l1, l2 *ListNode) *ListNode {
|
||
dummy := &ListNode{}
|
||
tail := dummy
|
||
|
||
for l1 != nil && l2 != nil {
|
||
if l1.Val <= l2.Val {
|
||
tail.Next = l1 // 选较小的节点接到末尾
|
||
l1 = l1.Next
|
||
} else {
|
||
tail.Next = l2
|
||
l2 = l2.Next
|
||
}
|
||
tail = tail.Next
|
||
}
|
||
|
||
// 接上剩余部分（至少有一条链表为空）
|
||
if l1 != nil {
|
||
tail.Next = l1
|
||
} else {
|
||
tail.Next = l2
|
||
}
|
||
|
||
return dummy.Next
|
||
}
|
||
```
|
||
|
||
**时间复杂度：O(n log n)** — 共 log n 层递归，每层所有合并操作的总代价为 O(n)。
|
||
**空间复杂度：O(log n)** — 递归调用栈的最大深度等于归并树的高度，为 log n。
|
||
|
||
> [!tip] 🔧 本地测试辅助函数
|
||
> 以下辅助函数可以将切片与链表互相转换，方便编写单元测试：
|
||
|
||
```go
|
||
// sliceToList: 将切片转为链表，方便构造测试用例
|
||
func sliceToList(vals []int) *ListNode {
|
||
dummy := &ListNode{}
|
||
tail := dummy
|
||
for _, v := range vals {
|
||
tail.Next = &ListNode{Val: v}
|
||
tail = tail.Next
|
||
}
|
||
return dummy.Next
|
||
}
|
||
|
||
// listToSlice: 将链表转为切片，方便打印验证结果
|
||
func listToSlice(head *ListNode) []int {
|
||
var result []int
|
||
for head != nil {
|
||
result = append(result, head.Val)
|
||
head = head.Next
|
||
}
|
||
return result
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 148 题，通过率约 55%+。递归归并排序是面试中最常用的解答——它完美契合"链表适合顺序访问"的特性，代码量适中（~25 行），且能在面试现场流畅推导。建议在 15 分钟内能白板写出。
|
||
|
||
---
|
||
|
||
### 方法二：自底向上归并排序（迭代）🏆（严格 O(1) 空间）
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func sortList(head *ListNode) *ListNode {
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
|
||
// ① 计算链表长度
|
||
n := 0
|
||
for node := head; node != nil; node = node.Next {
|
||
n++
|
||
}
|
||
|
||
// 虚拟头节点：统一处理，无需对首节点特殊判断
|
||
dummy := &ListNode{Next: head}
|
||
|
||
// ② 自底向上，逐层扩大合并区间的大小
|
||
for gap := 1; gap < n; gap *= 2 {
|
||
prev, cur := dummy, dummy
|
||
|
||
// 从头到尾扫描，每次取两段长度为 gap 的子链表合并
|
||
for cur.Next != nil {
|
||
// 从 cur.Next 开始取 gap 个节点为第 1 段
|
||
h1, t1 := split(cur.Next, gap)
|
||
// 从 t1.Next 开始取 gap 个节点为第 2 段
|
||
h2, t2 := split(t1.Next, gap)
|
||
// 保存下一组数据的起点
|
||
nextGroup := t2.Next
|
||
|
||
// 合并两段
|
||
t1.Next, t2.Next = nil, nil
|
||
merged := merge(h1, h2)
|
||
|
||
// 将合并后的链表接回主链表
|
||
prev.Next = merged
|
||
|
||
// prev 更新到合并后链表的尾部
|
||
prev = t1
|
||
if merged != h1 {
|
||
prev = t2
|
||
}
|
||
|
||
// cur 跳到下一组
|
||
cur = nextGroup
|
||
}
|
||
}
|
||
|
||
return dummy.Next
|
||
}
|
||
|
||
// split 从 head 开始截取最多 length 个节点
|
||
// 返回值：(段头, 段尾的下一个节点)
|
||
// 并将段尾的 Next 设为 nil（切断）
|
||
func split(head *ListNode, length int) (*ListNode, *ListNode) {
|
||
if head == nil {
|
||
return nil, nil
|
||
}
|
||
|
||
h := head
|
||
t := head
|
||
for i := 1; i < length && t.Next != nil; i++ {
|
||
t = t.Next
|
||
}
|
||
|
||
next := t.Next // 记录切断后的下一段起点
|
||
t.Next = nil // 切断
|
||
|
||
return h, next
|
||
}
|
||
|
||
// merge 合并两个有序链表
|
||
func merge(l1, l2 *ListNode) *ListNode {
|
||
dummy := &ListNode{}
|
||
tail := dummy
|
||
|
||
for l1 != nil && l2 != nil {
|
||
if l1.Val <= l2.Val {
|
||
tail.Next = l1
|
||
l1 = l1.Next
|
||
} else {
|
||
tail.Next = l2
|
||
l2 = l2.Next
|
||
}
|
||
tail = tail.Next
|
||
}
|
||
|
||
if l1 != nil {
|
||
tail.Next = l1
|
||
} else {
|
||
tail.Next = l2
|
||
}
|
||
|
||
return dummy.Next
|
||
}
|
||
```
|
||
|
||
**时间复杂度：O(n log n)** — gap 从 1 倍增到 n，共 log n 轮，每轮遍历全链表 O(n)。
|
||
**空间复杂度：O(1)** — 只使用了常数个指针变量，无递归调用栈。
|
||
|
||
> [!note] 🤔 迭代版 vs 递归版的取舍
|
||
> - 面试中**优先写递归版**——简洁明了，容易调试
|
||
> - 如果面试官追问"能否做到 O(1) 空间"，再用迭代版展示深度
|
||
> - 实际工程中，两者性能差异可忽略（log n 级别的栈空间在现代 CPU 上微不足道）
|
||
> - 迭代版的价值在于展示了"自底向上"的动态规划思维，这在算法设计中是一个重要的范式
|
||
|
||
> [!warning] ⚠️ 迭代版的关键细节
|
||
> 1. **`dummy` 节点必须在外层循环外创建一次**，而非每层新建——这样才能把所有层合并的结果串联起来
|
||
> 2. **`prev` 需要更新到合并后链表的尾部**，而不是简单地 `prev = prev.Next`。因为合并可能改变长度（两段等长则合并后长度为 2*gap，prev 需要前进到这个新段末尾）
|
||
> 3. **`nextGroup` 必须在合并前保存**——因为 `split` 会修改节点的 `Next` 指针
|