在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下闷煤，對(duì)鏈表進(jìn)行排序岖免。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
python3解答
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
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 if left else right
return res.next
