148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

来源：力扣（LeetCode）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        a=[]
        p=head
        while p:
            a.append(p.val)
            p=p.next
        a.sort()
        i=0
        p=head
        while p:
            p.val=a[i]
            p=p.next
            i+=1
        return head

 归并排序

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:return head
        mid = self.getMid(head)
        left = head
        right = mid.next
        mid.next=None
        l=self.sortList(left)
        r=self.sortList(right)
        return self.merge(l,r)
    
    def getMid(self,head):
        slow=head
        fast=head
        while fast.next and fast.next.next:
            slow=slow.next
            fast=fast.next.next
        return slow
    
    def merge(self,l,r):
        dummy=ListNode(None)
        cur=dummy
        while l and r:
            if l.val<=r.val:
                cur.next=l
                l=l.next
            else:
                cur.next=r
                r=r.next
            cur=cur.next
        cur.next=l or r
        return dummy.next