题目描述
给你链表的头结点 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
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
思路
归并排序
归并解法
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
fast, slow = fast.next.next, slow.next
mid, slow.next = slow.next, None
left, right = self.sortList(head), self.sortList(mid)
h = res = ListNode(0)
while left and right:
if left.val < right.val:
h.next, left = left, left.next
else:
h.next, right = right, right.next
h = h.next
h.next = left or right
return res.next
