LeetCode-Go 题解：148. Sort List 链表归并排序——O(n log n) 时间、O(1) 空间的 Go 实现

LeetCode-Go 题解：148. Sort List 链表归并排序——O(n log n) 时间、O(1) 空间的 Go 实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

LeetCode 148. Sort List 要求在 O(n log n) 时间复杂度和 O(1) 常数空间复杂度内对单链表完成排序。由于链表不具备随机访问能力，经典的快速排序与堆排序都难以达到约束要求，唯一可行的方案是归并排序（Merge Sort）。本篇文章以 LeetCode-Go 仓库中 0148.Sort-List 一题的官方题解文档与源码为核心，讲解链表归并排序的完整实现思路：如何用快慢指针寻找链表中点、如何递归拆分、如何合并两个有序链表，并结合仓库测试用例与数据结构工具验证实现的正确性。读完本文，你将掌握链表场景下归并排序的完整落地写法，以及它与第 876 题、第 21 题之间的代码复用关系。

一、题目理解：链表的排序约束

原题要求如下（见 0148.Sort-List.md）：

Sort a linked list in O(n log n) time using constant space complexity.

即：对单链表排序，时间复杂度必须为 O(n log n)，空间复杂度必须为 O(1)。

两个官方示例：

Input: 4->2->1->3 Output: 1->2->3->4 Input: -1->5->3->4->0 Output: -1->0->3->4->5

为什么数组上的常规排序算法在这里行不通？

• 快速排序：平均 O(n log n)，但最坏退化到 O(n²)，且分区需要前后指针双向扫描，对只能单向遍历的链表而言难以高效实现；
• 堆排序：虽然复杂度稳定为 O(n log n)，但需要随机访问，链表无法直接构建高效的二叉堆；
• 插入排序、选择排序：复杂度为 O(n²)，不满足时间要求。

排除掉上述方案后，归并排序成为唯一符合要求的选择：它的时间稳定为 O(n log n)，空间上只需要递归栈（配合合理的递归写法，可以视为常数辅助空间），并且只需要单向遍历，天然适配链表的物理结构。

二、解题思路：用归并排序满足全部约束

原文档明确给出了本题的核心结论：

This problem can only use merge sort to meet the requirements. The 2 operations needed for merge sort have already appeared in other problems: finding the middle point is Problem 876, and merging 2 sorted linked lists is Problem 21.

链表归并排序可以拆解为三步：

1. 找中点（split）：用快慢指针找到链表的中间节点，将链表从中间一分为二；
2. 递归排序：分别对左右两半递归执行sortList；
3. 合并（merge）：将两个已排序的子链表合并成一个有序链表。

递归的终止条件是链表为空或仅有一个节点——此时链表天然有序，直接返回。

有意思的是，这三步中的"找中点"与"合并两个有序链表"两个子操作，正是 LeetCode-Go 仓库中 0876.Middle-of-the-Linked-List 和 0021.Merge-Two-Sorted-Lists 两题的核心算法。因此本题可以视为这两道题的组合应用。

快慢指针找中点：为什么返回"前一个中间节点"

LeetCode 876 题要求"若有偶数个节点，返回后一个中间节点"，因此它在循环结束后做了奇偶判断：

// 876. Middle of the Linked List 的中间节点实现（截选） func middleNode(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } p1 := head p2 := head for p2.Next != nil && p2.Next.Next != nil { p1 = p1.Next p2 = p2.Next.Next } length := 0 cur := head for cur != nil { length++ cur = cur.Next } if length%2 == 0 { return p1.Next // 偶数长度返回后一个中点 } return p1 }

而148 题的目的不是"找到中间节点"，而是"把链表从中间拆成两半"，所以它直接返回慢指针p1（偶数长度时是前一个中间节点）。这样middleNode.Next恰好是右半段的头节点，将其置空即可完成拆分，无需再像 876 题那样做奇偶特判。这是两题在细节上最关键的区别，源码见 148. Sort List.go 与 876. Middle of the Linked List.go。

三、完整 Go 实现与逐行剖析

原文档给出的核心实现如下（与仓库源码 148. Sort List.go 一致）：

func sortList(head *ListNode) *ListNode { length := 0 cur := head for cur != nil { length++ cur = cur.Next } if length <= 1 { return head } middleNode := middleNode(head) cur = middleNode.Next middleNode.Next = nil middleNode = cur left := sortList(head) right := sortList(middleNode) return mergeTwoLists(left, right) } func middleNode(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } p1 := head p2 := head for p2.Next != nil && p2.Next.Next != nil { p1 = p1.Next p2 = p2.Next.Next } return p1 } func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 } l2.Next = mergeTwoLists(l1, l2.Next) return l2 }

3.1 sortList：递归主流程

• 第一步，统计链表长度：先遍历一次链表计算总长度。这一步有两个作用：其一，length <= 1时直接返回，作为递归终止条件；其二，在实现层面保证对任意输入都能正确终止（比单独判head == nil || head.Next == nil更稳健）。
• 第二步，拆分：调用middleNode找到左半段的末尾节点，取middleNode.Next作为右半段头节点，然后把middleNode.Next置为nil，将链表真正切断为两段互不相干的子链表。
• 第三步，递归与合并：对head（左半段）和middleNode（右半段）分别递归排序，最后用mergeTwoLists合并返回。

3.2 middleNode：快慢指针一次遍历取中点

慢指针p1每次走 1 步，快指针p2每次走 2 步。循环条件p2.Next != nil && p2.Next.Next != nil保证快指针不会越界。当快指针到达或越过链表末尾时，慢指针恰好停在左半段的最后一个节点上：

• 长度为奇数（如 5）时，p1落在第 3 个节点上（即正中间），右半段从第 4 个节点开始；
• 长度为偶数（如 6）时，p1落在第 3 个节点上（即左半段末尾），右半段从第 4 个节点开始。

无论奇偶，p1都是左半段末尾，拆分逻辑完全统一。此外，middleNode对nil和单节点输入做了守卫（直接返回自身），这一点在测试中也有专门覆盖。

3.3 mergeTwoLists：递归合并两个有序链表

这是标准的归并过程：比较两个链表当前头节点的值，取较小者作为结果链表的头，然后递归合并剩余部分。两个基准情形（l1 == nil返回l2，l2 == nil返回l1）处理了任一链表耗尽的情况。该实现与 21. Merge Two Sorted Lists.go 中的mergeTwoLists完全一致，验证了原文档"合并操作复用第 21 题"的说法。

四、复杂度分析

五、边界情况与测试验证

仓库中的测试文件 148. Sort List_test.go 采用表驱动测试（table-driven test），通过question148结构体组织参数与期望答案，覆盖了以下几类典型场景：

测试中还针对middleNode的守卫分支做了专门断言：

// cover middleNode guard branch: nil and single-node inputs if middleNode(nil) != nil { t.Fatalf("middleNode(nil) should return nil") } single := structures.Ints2List([]int{1}) if middleNode(single) != single { t.Fatalf("middleNode(single) should return the same node") }

5.1 链表与切片的转换工具

测试通过仓库公共数据结构包 structures/ListNode.go 提供的两个工具函数完成输入输出转换：

• Ints2List(nums []int) *ListNode：将[]int顺序构造成单链表，空切片返回nil；
• List2Ints(head *ListNode) []int：将链表还原为[]int以便与期望结果比较。该函数内置了 100 层深度上限，防止环状链表导致死循环——从侧面说明仓库对测试安全性的重视。

ListNode结构定义如下（与 LeetCode 官方定义一致）：

type ListNode struct { Val int Next *ListNode }

5.2 如何运行测试

仓库根目录的 gotest.sh 提供了全量测试脚本，其核心命令是对./leetcode/...一次性执行带覆盖率统计的测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

若只想验证本题，可单独运行：

go test -v -run Test_Problem148 ./leetcode/0148.Sort-List/

运行后会在终端打印如下形式的输入输出对照（来自测试代码中的fmt.Printf）：

【input】:[1 1 2 5 5 4 10 0] 【output】:[...已排序结果...]

六、与仓库中 21、876 题的源码对照

原文档特别指出本题的两个子操作分别来自第 876 题和第 21 题，仓库源码也印证了这一说法：

1. 合并操作完全复用：148. Sort List.go 中的mergeTwoLists与 21. Merge Two Sorted Lists.go 中的同名函数逐行一致；
2. 取中点操作同源但细节不同：876. Middle of the Linked List.go 中的middleNode因题目要求"偶数长度返回第二个中间节点"，在循环后做了length%2判断；而 148 题的middleNode为满足拆分需求，直接返回左半段末尾节点。两者快慢指针的核心遍历逻辑相同，仅在返回值语义上有差异。

这种"一道题复用多道题算法"的组织方式，正是 LeetCode-Go 仓库题解的特点：把高频子算法沉淀成独立可复用的解法，再在不同题目中组合应用。

七、小结

LeetCode 148 题是链表算法中"复杂约束逼出唯一解"的典型范例：O(n log n) + O(1) 的硬性要求，排除了快排与堆排序，只剩下归并排序一条路。掌握本题后，你实际上同时掌握了三道题的解法：

• 找链表中点（快慢指针，对应 876 题）；
• 合并两个有序链表（对应 21 题）；
• 链表归并排序的递归拆分与原地合并（本题核心）。

实战时只需记住两个关键点：middleNode返回的是左半段末尾节点（便于切断链表），以及合并阶段通过修改Next指针原地拼接（保证常数空间）。配合仓库的表驱动测试与gotest.sh一键运行，可以快速验证实现正确性。

// 最终可运行的核心代码（完整版见 leetcode/0148.Sort-List/148. Sort List.go） func sortList(head *ListNode) *ListNode { length := 0 for cur := head; cur != nil; cur = cur.Next { length++ } if length <= 1 { return head } middle := middleNode(head) right := middle.Next middle.Next = nil return mergeTwoLists(sortList(head), sortList(right)) }

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go