148. 排序链表

https://leetcode-cn.com/problems/sort-list/

解法一：归并排序

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        return self.mergeSort(head)
    
    def mergeSort(self, head):
        if not head.next:
            return head
        slow = fast = head
        pre = None    #指向slow前驱
        #快慢指针找中点
        while fast and fast.next:
            pre = slow
            fast = fast.next.next
            slow = slow.next
        pre.next = None    #截断,后半段从slow开始
        left = self.mergeSort(head)
        right = self.mergeSort(slow)
        return self.merge(left, right)
        
    #合并两个有序链表
    def merge(self, l, r):
        Head = ListNode(None)
        cur = Head
        while l and r:
            if l.val <= r.val:
                cur.next = l
                cur = cur.next
                l = l.next
            else:
                cur.next = r
                cur = cur.next
                r = r.next
        #此时最多只有一个空的
        #若r不空，直接连r；
        #若r空，连l
        cur.next = l if not r else r
        return Head.next