题解 | #单链表的排序#

单链表的排序，归并排序超时

class Solution:
    def sortInList(self , head ):
        # write code here
        if head is None or head.next is None:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
        new_list = slow.next
        slow.next = None
        left = self.sortInList(head)
        right = self.sortInList(new_list)
        dummy = ListNode(0)
        p = dummy
        while left and right:
            if left.val < right.val:
                p.next = left
                left = left.next
            else:
                p.next = right
                right = right.next
            p = p.next
        p.next = left if left is not None else right
        return dummy.next