LeetCode 148. 排序链表解法一自顶向下归并排序递归思路用快慢指针找中点将链表拆成两半递归排序后合并。# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:# 递归终止空链表或只有一个节点ifnotheadornothead.next:returnhead# 快慢指针找中点slow 停在左半部分末尾slow,fasthead,head.nextwhilefastandfast.next:slowslow.nextfastfast.next.next# 断开链表midslow.nextslow.nextNone# 递归排序左右两半leftself.sortList(head)rightself.sortList(mid)# 合并两个有序链表returnself.merge(left,right)defmerge(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummyListNode(0)curdummywhilel1andl2:ifl1.vall2.val:cur.nextl1 l1l1.nextelse:cur.nextl2 l2l2.nextcurcur.nextcur.nextl1ifl1elsel2returndummy.next复杂度· 时间 O(n log n)· 空间 O(log n)递归栈解法二自底向上归并排序迭代空间 O(1)思路不需要递归按步长 step 1, 2, 4, … 逐层两两合并子链表。classSolution:defsortList(self,head:Optional[ListNode])-Optional[ListNode]:ifnotheadornothead.next:returnhead# 计算链表长度length0nodeheadwhilenode:length1nodenode.nextdummyListNode(0,head)step1whilesteplength:prev,curdummy,dummy.nextwhilecur:# 找左半部分长度为 stepleftcurfor_inrange(step-1):ifcur.next:curcur.nextelse:breakrightcur.nextcur.nextNone# 断开左半部分# 找右半部分长度最多为 stepcurrightfor_inrange(step-1):ifcurandcur.next:curcur.nextelse:break# 断开右半部分记录下一轮起点nxtNoneifcur:nxtcur.nextcur.nextNone# 合并左右两半接到 prev 后prev.nextself.merge(left,right)whileprev.next:prevprev.nextcurnxt step*2returndummy.nextdefmerge(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:dummyListNode(0)curdummywhilel1andl2:ifl1.vall2.val:cur.nextl1 l1l1.nextelse:cur.nextl2 l2l2.nextcurcur.nextcur.nextl1ifl1elsel2returndummy.next复杂度· 时间 O(n log n)· 空间 O(1)满足题目「常数级空间」的进阶要求要点总结方法 时间 空间 特点自顶向下递归 O(n log n) O(log n) 代码简洁易理解自底向上迭代 O(n log n) O(1) 满足进阶要求关键技巧快慢指针找中点时fast 初始化成 head.next可让 slow 停在左半段末尾偶数节点时左半段更短。断开链表后再递归/合并避免死循环。dummy 头节点简化合并逻辑。数组快排常用但链表首选归并——链表合并只需 O(1) 额外空间且随机访问代价高不适合快排。
