 时间、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.mdSort 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.链表归并排序可以拆解为三步找中点split用快慢指针找到链表的中间节点将链表从中间一分为二递归排序分别对左右两半递归执行sortList合并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返回l2l2 nil返回l1处理了任一链表耗尽的情况。该实现与 21. Merge Two Sorted Lists.go 中的mergeTwoLists完全一致验证了原文档合并操作复用第 21 题的说法。四、复杂度分析指标分析时间复杂度归并排序每一层需要 O(n) 的合并操作递归树深度为 O(log n)总计 O(n log n)满足题目约束空间复杂度合并过程通过修改Next指针原地拼接不申请额外数组唯一的辅助开销是递归调用栈 O(log n)。在 LeetCode 判定语境下可视为常数空间 O(1)满足题目约束稳定性归并排序是稳定排序相等元素的相对顺序在合并时保持不变l1.Val l2.Val取前者相等时优先取左链表五、边界情况与测试验证仓库中的测试文件 148. Sort List_test.go 采用表驱动测试table-driven test通过question148结构体组织参数与期望答案覆盖了以下几类典型场景测试输入场景类型[1, 2, 3, 4, 5]已升序排列的链表[1, 1, 2, 5, 5, 4, 10, 0]乱序且含重复元素的链表[1]单节点链表递归终止分支[]空链表递归终止分支测试中还针对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顺序构造成单链表空切片返回nilList2Ints(head *ListNode) []int将链表还原为[]int以便与期望结果比较。该函数内置了 100 层深度上限防止环状链表导致死循环——从侧面说明仓库对测试安全性的重视。ListNode结构定义如下与 LeetCode 官方定义一致type ListNode struct { Val int Next *ListNode }5.2 如何运行测试仓库根目录的 gotest.sh 提供了全量测试脚本其核心命令是对./leetcode/...一次性执行带覆盖率统计的测试go test -covermodeatomic -coverprofilecoverage.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 题仓库源码也印证了这一说法合并操作完全复用148. Sort List.go 中的mergeTwoLists与 21. Merge Two Sorted Lists.go 中的同名函数逐行一致取中点操作同源但细节不同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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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.mdSort 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.链表归并排序可以拆解为三步找中点split用快慢指针找到链表的中间节点将链表从中间一分为二递归排序分别对左右两半递归执行sortList合并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返回l2l2 nil返回l1处理了任一链表耗尽的情况。该实现与 21. Merge Two Sorted Lists.go 中的mergeTwoLists完全一致验证了原文档合并操作复用第 21 题的说法。四、复杂度分析指标分析时间复杂度归并排序每一层需要 O(n) 的合并操作递归树深度为 O(log n)总计 O(n log n)满足题目约束空间复杂度合并过程通过修改Next指针原地拼接不申请额外数组唯一的辅助开销是递归调用栈 O(log n)。在 LeetCode 判定语境下可视为常数空间 O(1)满足题目约束稳定性归并排序是稳定排序相等元素的相对顺序在合并时保持不变l1.Val l2.Val取前者相等时优先取左链表五、边界情况与测试验证仓库中的测试文件 148. Sort List_test.go 采用表驱动测试table-driven test通过question148结构体组织参数与期望答案覆盖了以下几类典型场景测试输入场景类型[1, 2, 3, 4, 5]已升序排列的链表[1, 1, 2, 5, 5, 4, 10, 0]乱序且含重复元素的链表[1]单节点链表递归终止分支[]空链表递归终止分支测试中还针对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顺序构造成单链表空切片返回nilList2Ints(head *ListNode) []int将链表还原为[]int以便与期望结果比较。该函数内置了 100 层深度上限防止环状链表导致死循环——从侧面说明仓库对测试安全性的重视。ListNode结构定义如下与 LeetCode 官方定义一致type ListNode struct { Val int Next *ListNode }5.2 如何运行测试仓库根目录的 gotest.sh 提供了全量测试脚本其核心命令是对./leetcode/...一次性执行带覆盖率统计的测试go test -covermodeatomic -coverprofilecoverage.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 题仓库源码也印证了这一说法合并操作完全复用148. Sort List.go 中的mergeTwoLists与 21. Merge Two Sorted Lists.go 中的同名函数逐行一致取中点操作同源但细节不同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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考