分治

副标题 / 摘要 LeetCode 148 的核心不是“会排序”，而是“在链表结构里选对排序算法”。数组可随机访问适合快排/堆排，而单链表最匹配的是归并排序：找中点、递归分治、线性归并。 预计阅读时长：12~16 分钟 标签：Hot100、链表、归并排序、分治 SEO 关键词：Sort List, 排序链表, 链表归并排序, LeetCode 148, Hot100 元描述：用链表归并排序在 O(n log n) 内完成排序，覆盖思路推导、工程迁移、复杂度分析和多语言可运行实现。 目标读者 正在刷 Hot100，想把链表题模板系统化的同学 做链表题经常在“切分和拼接”环节出错的开发者 想搞清楚“为什么链表排序优先用归并”而不是快排的人 背景 / 动机 链表排序在工程里并不罕见： 合并来自多个来源的链式任务队列 对按时间追加的链式日志做离线整理 对内存敏感结构进行“尽量少拷贝”的重排 如果把数组排序思维直接搬过来，往往会遇到： 链表不支持 O(1) 随机访问，分区/堆操作代价高 频繁节点移动容易写出复杂且脆弱的代码 所以这题本质是：为链表选择正确的数据结构友好算法。 核心概念 分治（Divide & Conquer）：把链表二分到最小子问题，再向上合并 快慢指针找中点：slow 每次 1 步，fast 每次 2 步 链表归并：两个有序链表线性拼接成一个有序链表 稳定排序：相等元素相对次序可保持 A — Algorithm（题目与算法） 题目还原 给你链表头节点 head，请将其按升序排序并返回排序后的链表。 要求时间复杂度为 O(n log n)。 输入输出 名称 类型 描述 head ListNode 单链表头节点（可能为空） 返回 ListNode 升序排序后的头节点 示例 1 输入: 4 -> 2 -> 1 -> 3 输出: 1 -> 2 -> 3 -> 4 示例 2 输入: -1 -> 5 -> 3 -> 4 -> 0 输出: -1 -> 0 -> 3 -> 4 -> 5 思路推导（从朴素到最优） 朴素做法：转数组再排序 遍历链表把值放到数组 调库排序后重建链表 问题： ...

副标题 / 摘要 这题本质是“k 路归并”。如果直接一条条串行并入，性能会退化；用分治按二叉树方式两两合并，能把复杂度优化到 O(N log k)。本文按 ACERS 模板把思路推导、工程映射和多语言实现一次讲透。 预计阅读时长：12~16 分钟 标签：Hot100、链表、分治、归并 SEO 关键词：Merge k Sorted Lists, 合并K个升序链表, 分治归并, LeetCode 23, O(N log k) 元描述：从串行归并到分治归并，系统讲解 LeetCode 23 的最优复杂度解法与工程实践。 目标读者 正在刷 Hot100，已经掌握 LeetCode 21 的同学 想把“双链表归并”升级为“k 路归并模板”的开发者 在服务端做多路有序流合并（日志、时间线、分片结果）的工程师 背景 / 动机 LeetCode 23 是 LeetCode 21 的自然升级版： 21：2 路归并 23：k 路归并 核心挑战不在“能不能合并”，而在“如何把复杂度控制在可接受范围”。 如果每次把结果链表继续和下一条链表做串行归并，早期节点会被反复遍历，实际性能很容易退化。 核心概念 N：所有链表节点总数 k：链表条数 串行归并：从左到右不断把当前结果和下一条链表合并 分治归并：像归并排序一样，两两合并，按层收敛 最小堆方案：维护 k 个当前头节点，每次弹出最小值并推进其所在链表 A — Algorithm（题目与算法） 题目还原 给你一个链表数组 lists，每个链表都按升序排列。 请将所有链表合并到一个升序链表中，并返回合并后的头节点。 输入输出 名称 类型 描述 lists ListNode[] k 条升序链表，元素可为空 返回 ListNode 合并后的升序链表头节点 示例 1 输入: lists = [[1,4,5],[1,3,4],[2,6]] 输出: [1,1,2,3,4,4,5,6] 示例 2 输入: lists = [] 输出: [] C — Concepts（核心思想） 思路推导：从朴素到最优 朴素法 A：拉平到数组后排序 ...