[特殊字符] 第30课：排序链表

想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第30课排序链表模块链表 |难度Medium ⭐⭐LeetCode 链接https://leetcode.cn/problems/sort-list/前置知识第25课(合并两个有序链表)、第29课(快慢指针找中点)预计学习时间30分钟 题目描述给你链表的头节点head,请将其按升序排列并返回排序后的链表。进阶要求你能否在O(n log n)时间复杂度和O(1)空间复杂度下完成示例输入head [4,2,1,3] 输出[1,2,3,4]输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]约束条件链表节点数范围是[0, 50000]-100000 Node.val 100000 边界用例面试必考用例类型输入期望输出考察点空链表headnullnull边界处理单节点head[1][1]递归终止条件已排序head[1,2,3,4][1,2,3,4]最优情况逆序head[4,3,2,1][1,2,3,4]最坏情况有重复head[3,1,2,3,1][1,1,2,3,3]稳定性大规模50000个节点—性能边界 思路引导生活化比喻想象你要把一副打乱的扑克牌排序…笨办法把所有牌从桌上拿到手里(转成数组),在手里排好序(Array.sort),再一张张放回桌上(转回链表)。这样做简单,但需要额外的空手空间(额外 O(n) 空间)。聪明办法用归并排序的思想——把牌分成两堆,分别排序,然后合并。就像整理两叠已排序的文件,从两堆的第一张开始比较,每次取较小的那张放入结果堆。递归地分治,直到每堆只有一张牌(天然有序),然后逐层合并。这样只需要在桌面上移动牌,不用额外空间关键洞察链表排序首选归并排序,因为链表不支持随机访问,无法高效使用快速排序!归并排序的关键操作——找中点、合并两个有序链表——都可以 O(1) 空间完成。 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1理解题目 → 锁定输入输出输入无序链表的头节点head输出排序后的链表头节点限制进阶要求 O(n log n) 时间 O(1) 空间Step 2先想笨办法暴力法最直接的思路:遍历链表,把所有值存到数组中 — O(n)对数组排序 — O(n log n)遍历数组,重新构建链表 — O(n)时间复杂度O(n log n) ✅空间复杂度O(n) ❌ (不符合进阶要求的 O(1) 空间)瓶颈在哪需要额外 O(n) 数组空间存储所有节点值Step 3瓶颈分析 → 优化方向分析暴力法的核心问题:核心问题数组排序需要额外空间,能否直接在链表上原地排序排序算法选择快速排序需要随机访问,链表不支持 → ❌堆排序需要数组结构建堆 → ❌归并排序只需顺序访问 合并操作,完美适配链表 → ✅优化思路使用归并排序,链表天然支持分割和合并操作,可以做到 O(1) 空间Step 4选择武器选用归并排序自顶向下递归理由归并排序的分治过程只需要找中点快慢指针 O(1) 空间合并两个有序链表可以 O(1) 空间完成第25课学过时间复杂度 O(n log n),递归栈深度 O(log n) 空间还不是 O(1)终极优化归并排序的自底向上迭代版本→ O(1) 空间模式识别提示当题目要求排序链表,且需要 O(n log n) 时间,优先考虑归并排序 解法一转数组排序暴力思路把链表转成数组,用 Python 内置排序,再转回链表。简单直接,但空间复杂度 O(n)。图解过程示例: head [4,2,1,3] Step 1: 遍历链表,转成数组 4 - 2 - 1 - 3 - null ↓ arr [4, 2, 1, 3] Step 2: 排序数组 arr.sort() → [1, 2, 3, 4] Step 3: 根据数组重建链表 1 - 2 - 3 - 4 - null 返回新链表的头节点Python代码fromtypingimportOptionalclassListNode:def__init__(self,val0,nextNone):self.valval self.nextnextdefsortList(head:Optional[ListNode])-Optional[ListNode]: 解法一转数组排序 思路链表 → 数组 → 排序 → 链表 ifnothead:returnNone# Step 1: 链表转数组values[]currheadwhilecurr:values.append(curr.val)currcurr.next# Step 2: 排序数组values.sort()# Step 3: 重建链表dummyListNode(0)currdummyforvalinvalues:curr.nextListNode(val)currcurr.nextreturndummy.next# ✅ 测试辅助函数defcreate_linked_list(values):根据列表创建链表dummyListNode(0)currdummyforvalinvalues:curr.nextListNode(val)currcurr.nextreturndummy.nextdeflinked_list_to_list(head):将链表转为列表result[]whilehead:result.append(head.val)headhead.nextreturnresult# ✅ 测试head1create_linked_list([4,2,1,3])print(linked_list_to_list(sortList(head1)))# 期望输出[1, 2, 3, 4]head2create_linked_list([-1,5,3,4,0])print(linked_list_to_list(sortList(head2)))# 期望输出[-1, 0, 3, 4, 5]head3create_linked_list([])print(linked_list_to_list(sortList(head3)))# 期望输出[]复杂度分析时间复杂度O(n log n) — Python 的 Timsort 排序算法具体地说如果链表有 1000 个节点,Timsort 大约需要 1000 * log₂(1000) ≈ 10000 次比较空间复杂度O(n) — 需要数组存储所有节点值优缺点✅ 代码简单,易于实现✅ 利用 Python 内置高效排序❌额外 O(n) 空间,不符合进阶要求⚡ 解法二归并排序自顶向下递归优化思路归并排序的核心思想:分治法分找到链表中点,分成两个子链表治递归地对两个子链表排序合合并两个有序链表关键操作:找中点快慢指针第29课学过合并有序链表第25课学过的技巧关键想法递归终止条件是链表只有 0 或 1 个节点,此时天然有序,直接返回。图解过程示例: head [4,2,1,3] 第1层分治: 分成两半 [4, 2, 1, 3] ↓ (找中点) [4, 2] 和 [1, 3] 第2层分治: 继续分 [4, 2] → [4] 和 [2] [1, 3] → [1] 和 [3] 递归终止: 单节点天然有序 [4], [2], [1], [3] 第1次合并: 两两合并 merge([4], [2]) → [2, 4] merge([1], [3]) → [1, 3] 第2次合并: 最终合并 merge([2, 4], [1, 3]) → [1, 2, 3, 4] 返回 [1, 2, 3, 4]详细演示merge 过程合并 [2, 4] 和 [1, 3]: 初始: L1: 2 - 4 - null L2: 1 - 3 - null result: dummy Step 1: 比较 2 和 1, 取 1 dummy - 1 L2 前进到 3 Step 2: 比较 2 和 3, 取 2 dummy - 1 - 2 L1 前进到 4 Step 3: 比较 4 和 3, 取 3 dummy - 1 - 2 - 3 L2 到达末尾 Step 4: L1 剩余节点直接接上 dummy - 1 - 2 - 3 - 4 返回 dummy.nextPython代码defsortList_v2(head:Optional[ListNode])-Optional[ListNode]: 解法二归并排序自顶向下递归 思路分治法——找中点、递归排序、合并 # 递归终止条件空链表或单节点ifnotheadornothead.next:returnhead# Step 1: 找中点,分割链表midget_middle(head)right_headmid.nextmid.nextNone# 断开链表# Step 2: 递归排序两个子链表leftsortList_v2(head)rightsortList_v2(right_head)# Step 3: 合并两个有序链表returnmerge_two_lists(left,right)defget_middle(head:ListNode)-ListNode: 找链表中点快慢指针 当链表有偶数个节点时,返回前半部分的最后一个节点 slowhead fasthead.next# fast 从 head.next 开始,确保 slow 停在前半部分whilefastandfast.next:slowslow.nextfastfast.next.nextreturnslowdefmerge_two_lists(l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]: 合并两个有序链表第25课学过 dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.next# 接上剩余节点curr.nextl1ifl1elsel2returndummy.next# ✅ 测试head1create_linked_list([4,2,1,3])print(linked_list_to_list(sortList_v2(head1)))# 期望输出[1, 2, 3, 4]head2create_linked_list([-1,5,3,4,0])print(linked_list_to_list(sortList_v2(head2)))# 期望输出[-1, 0, 3, 4, 5]复杂度分析时间复杂度O(n log n)递归树有 log n 层每次分割减半每层的合并操作总共处理 n 个节点总时间 n * log n空间复杂度O(log n) —递归栈深度还不是 O(1) 解法三归并排序自底向上迭代优化思路解法二使用递归,递归栈占用 O(log n) 空间。能否不用递归,改用迭代自底向上归并排序:第1轮每次合并长度为 1 的子链表 → 得到长度为 2 的有序段第2轮每次合并长度为 2 的子链表 → 得到长度为 4 的有序段第k轮每次合并长度为 2^(k-1) 的子链表 → 得到长度为 2^k 的有序段重复直到子链表长度 ≥ 链表总长度关键想法自底向上避免递归,用循环控制合并长度,每轮合并长度翻倍,最多 log n 轮。图解过程示例: head [4, 2, 1, 3] 初始链表: 4 - 2 - 1 - 3 第1轮 (step1): 合并长度为1的子链表 合并(4, 2) → [2, 4] 合并(1, 3) → [1, 3] 结果: 2 - 4 - 1 - 3 第2轮 (step2): 合并长度为2的子链表 合并([2,4], [1,3]) → [1, 2, 3, 4] 结果: 1 - 2 - 3 - 4 第3轮 (step4): step 链表长度,结束 返回 [1, 2, 3, 4]Python代码defsortList_v3(head:Optional[ListNode])-Optional[ListNode]: 解法三归并排序自底向上迭代 思路避免递归,用循环控制合并长度,实现 O(1) 空间 ifnotheadornothead.next:returnhead# 计算链表长度length0currheadwhilecurr:length1currcurr.nextdummyListNode(0,head)# 外层循环合并长度从 1 开始,每次翻倍step1whilesteplength:currdummy.next# 当前轮的起始节点taildummy# 用于连接已排序部分# 内层循环遍历链表,每次合并两个长度为 step 的子链表whilecurr:leftcurr rightsplit(left,step)# 分割出右半部分currsplit(right,step)# 下一对的起始位置# 合并 left 和 right,接到 tail 后面tailmerge_and_connect(left,right,tail)step*2# 合并长度翻倍returndummy.nextdefsplit(head:Optional[ListNode],step:int)-Optional[ListNode]: 从 head 开始走 step 步,然后断开,返回后半部分的头节点 for_inrange(step-1):ifnothead:breakheadhead.nextifnothead:returnNone# 断开链表next_headhead.nexthead.nextNonereturnnext_headdefmerge_and_connect(l1:Optional[ListNode],l2:Optional[ListNode],tail:ListNode)-ListNode: 合并 l1 和 l2,接到 tail 后面,返回合并后的尾节点 currtailwhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.next# 接上剩余节点curr.nextl1ifl1elsel2# 移动到尾节点whilecurr.next:currcurr.nextreturncurr# ✅ 测试head1create_linked_list([4,2,1,3])print(linked_list_to_list(sortList_v3(head1)))# 期望输出[1, 2, 3, 4]head2create_linked_list([-1,5,3,4,0])print(linked_list_to_list(sortList_v3(head2)))# 期望输出[-1, 0, 3, 4, 5]复杂度分析时间复杂度O(n log n)外层循环 log n 次step 从 1 翻倍到 n每轮内层循环处理 n 个节点空间复杂度O(1) —没有递归,只使用常数个指针✅ 满足进阶要求 Pythonic 写法归并排序的递归版本已经很简洁,但可以用 Python 的特性简化辅助函数defsortList_pythonic(head:Optional[ListNode])-Optional[ListNode]: Pythonic 写法利用 Python 的多重赋值 ifnotheadornothead.next:returnhead# 找中点并分割一气呵成slow,fasthead,head.nextwhilefastandfast.next:slow,fastslow.next,fast.next.nextmid,slow.nextslow.next,None# 断开链表,同时保存右半部分# 递归排序并合并returnmerge_two_lists(sortList_pythonic(head),sortList_pythonic(mid))这个写法的亮点用mid, slow.next slow.next, None同时保存右半部分和断开链表函数式风格:直接返回merge_two_lists(递归结果1, 递归结果2)⚠️面试建议自底向上迭代版本才是满足 O(1) 空间的完美解法,但代码较复杂。面试时可以先说递归版本思路,再提优化“如果要求 O(1) 空间,可以改成自底向上迭代”。 解法对比维度解法一转数组解法二归并递归解法三归并迭代时间复杂度O(n log n)O(n log n)O(n log n)空间复杂度O(n)O(log n)O(1)代码难度简单中等较难面试推荐⭐⭐⭐⭐⭐⭐⭐适用场景快速实现原型面试常规解法满足进阶要求面试建议先说解法一的思路,表明你理解了问题立即提出优化:“转数组需要额外空间,能否直接在链表上排序用归并排序”重点讲解解法二的递归版本,画出递归树,演示合并过程如果面试官追问 O(1) 空间,再提解法三的自底向上,并说明避免递归栈的思路 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官请你对链表进行排序,要求 O(n log n) 时间。你审题30秒好的,这道题要求对链表排序,并且时间复杂度是 O(n log n)。我的第一个想法是把链表转成数组,用 Python 内置的 sortTimsort,O(n log n),然后再转回链表。但这需要 O(n) 额外空间。更好的方法是用归并排序,因为归并排序天然适合链表:分割链表不需要随机访问,用快慢指针找中点即可合并两个有序链表可以 O(1) 空间完成核心思路是分治法:找中点,分成两个子链表递归排序两个子链表合并两个有序链表面试官很好,递归版本的空间复杂度是多少你递归版本的空间复杂度是 O(log n),因为递归栈的深度是 log n每次分割减半。如果题目要求 O(1) 空间,可以改用自底向上的迭代版本:第1轮合并长度为 1 的子链表第2轮合并长度为 2 的子链表每轮合并长度翻倍,最多 log n 轮这样避免了递归栈,实现 O(1) 空间。面试官请写一下递归版本的代码。你边写边说递归终止条件:空链表或单节点直接返回用快慢指针找中点,注意 fast 从 head.next 开始,确保 slow 停在前半部分断开链表,递归排序两个子链表调用 merge_two_lists 合并结果写完代码面试官测试一下你用示例 [4,2,1,3]:第1次分割 → [4,2] 和 [1,3]第2次分割 → [4], [2], [1], [3]单节点,递归终止第1次合并 → [2,4] 和 [1,3]第2次合并 → [1,2,3,4]结果正确。再测边界情况:空链表返回 null,单节点返回自身。高频追问追问应答策略“为什么不用快速排序”快速排序需要随机访问选 pivot 后要分区,链表不支持 O(1) 随机访问,会退化到 O(n²)。归并排序只需顺序访问,完美适配链表“归并排序是稳定排序吗”是。稳定排序指相等元素的相对顺序不变。归并排序的合并过程中,当 l1.val l2.val 时选 l1,保证了稳定性“如果链表非常大,内存有限怎么办”归并排序的自底向上版本是 O(1) 空间,已经是最优。如果链表大到内存放不下,需要外部排序分块、外排归并“能不能用堆排序”理论上可以,但需要用数组建堆,空间 O(n),且链表没有随机访问优势。归并排序更适合链表 知识点总结Python技巧卡片 # 技巧1: 快慢指针找中点偶数节点时返回前半部分最后一个slow,fasthead,head.nextwhilefastandfast.next:slow,fastslow.next,fast.next.next# slow 现在是中点# 技巧2: 同时赋值断开链表mid,slow.nextslow.next,None# 保存右半部分,同时断开# 技巧3: 递归函数直接返回调用结果函数式风格returnmerge_two_lists(sortList(head),sortList(mid))# 技巧4: 三元表达式简化条件选择curr.nextl1ifl1elsel2 底层原理选读为什么归并排序适合链表,快速排序不适合归并排序的关键操作:分割:链表找中点用快慢指针 O(n/2)合并:顺序遍历两个链表 O(n)都不需要随机访问,链表天然支持快速排序的关键操作:选 pivot:可以用链表头 O(1)分区partition:需要把小于 pivot 的放左边,大于的放右边链表的分区要么用额外空间两个新链表,要么需要频繁的指针操作,效率低数组的分区可以双指针交换,O(1) 空间 O(n) 时间时间复杂度对比:归并排序:链表和数组都是 O(n log n),稳定快速排序:数组平均 O(n log n),链表容易退化到 O(n²)无法随机选 pivot 避免最坏情况Python 的 Timsort 是什么Python 内置的list.sort()使用 Timsort 算法:结合了归并排序和插入排序的优点对部分有序数据性能极佳现实数据往往部分有序稳定排序,时间 O(n log n),空间 O(n)由 Tim Peters 在 2002 年为 Python 设计,现在也被 Java、Android 等采用算法模式卡片 模式名称归并排序链表版适用条件链表排序,要求 O(n log n) 时间识别关键词“链表排序”、“O(n log n)”、“稳定排序”核心思路分治法——递归分割链表,合并有序子链表模板代码defmergeSort(head):归并排序链表模板# 递归终止条件ifnotheadornothead.next:returnhead# 找中点并分割slow,fasthead,head.nextwhilefastandfast.next:slow,fastslow.next,fast.next.nextmidslow.nextslow.nextNone# 递归排序leftmergeSort(head)rightmergeSort(mid)# 合并returnmerge(left,right)defmerge(l1,l2):合并两个有序链表dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.nextcurr.nextl1ifl1elsel2returndummy.next易错点 ⚠️找中点时 fast 指针初始化错误❌ 错误slow fast head会导致 slow 停在后半部分的第一个节点✅ 正确slow head, fast head.next确保 slow 停在前半部分的最后一个节点原因如果 fast 从 head 开始,偶数节点时 slow 会偏右,导致递归无法终止右半部分长度不减少忘记断开链表❌ 错误找到中点后直接递归,不断开slow.next✅ 正确slow.next None断开链表,否则左半部分还连着右半部分,导致无限循环示例[1,2,3] 不断开会导致左半 [1,2,3],右半 [3],无法终止合并函数写成原地修改❌ 错误直接修改 l1 和 l2 的指针,可能导致原链表结构混乱✅ 正确创建虚拟头节点 dummy,构建新的有序链表,只移动 curr 指针递归终止条件不全❌ 错误只判断if not head:,遗漏单节点情况✅ 正确if not head or not head.next:,单节点也要直接返回已经有序️ 工程实战选读这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1数据库外部排序当数据库需要排序的数据量超过内存时,使用外部归并排序:先把数据分块排序写入磁盘,再多路归并。归并排序的稳定性和顺序访问特性使其成为外排的首选。场景2Git 版本控制Git 在合并分支时,底层使用归并排序合并两个有序的 commit 历史,保证时间线的稳定性相同时间戳的 commit 顺序不变。场景3日志文件合并多个服务器产生的日志文件按时间戳有序,需要合并成全局有序的日志流,使用多路归并类似合并 K 个有序链表,效率高且稳定。️ 举一反三完成本课后,试试这些同类题目来巩固知识题目难度相关知识点提示LeetCode 21. 合并两个有序链表Easy归并排序的合并步骤本题的子问题,先掌握合并再学排序LeetCode 23. 合并K个升序链表Hard多路归并 堆归并排序的扩展,用最小堆优化LeetCode 147. 对链表进行插入排序Medium插入排序小数据量时插入排序更简单LeetCode 剑指Offer 51. 数组中的逆序对Hard归并排序计数归并排序的副产品:统计逆序对 课后小测试试这道变体题,不要看答案,自己先想5分钟题目给定一个链表和一个值 x,将链表分成两部分,使得所有小于 x 的节点在大于等于 x 的节点之前,保持原有的相对顺序。LeetCode 86. 分隔链表 提示实在想不出来再点开用两个虚拟头节点,分别构建小于 x和大于等于 x的链表,最后拼接。类似归并排序的分区思想。✅ 参考答案defpartition(head:Optional[ListNode],x:int)-Optional[ListNode]: 分隔链表:小于 x 的在前,大于等于 x 的在后 # 创建两个虚拟头节点less_dummyListNode(0)greater_dummyListNode(0)lessless_dummy greatergreater_dummy# 遍历链表,分别接到两个链表whilehead:ifhead.valx:less.nexthead lessless.nextelse:greater.nexthead greatergreater.nextheadhead.next# 拼接两个链表greater.nextNone# 断开 greater 链表的尾部避免成环less.nextgreater_dummy.nextreturnless_dummy.next核心思路类似归并排序的分区思想,但更简单不需要递归用两个虚拟头节点分别存储小于和大于等于 x 的节点最后拼接两个链表,注意要断开 greater 的尾部避免成环时间 O(n),空间 O(1),稳定排序如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。