谷哇网站建设网络推广公司专业网络

148. 排序链表

问题：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：输入：head = []
输出：[]

提示：链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

解决：

归并排序链表

class Solution:def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:## 递归结束条件if not head or not head.next:return headslow,fast = head,head.next## 寻找中点并切分两个链表while fast and fast.next:fast,slow =fast.next.next, slow.nextmid,slow.next = slow.next,None## 归并排序l,r = self.sortList(head),self.sortList(mid)h=res=ListNode(0)while l and r:if l.val<r.val:h.next,l = l,l.nextelse:h.next,r = r,r.nexth=h.nexth.next=l if l else rreturn res.next