0148：排序链表（★）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def merge(a, b):
            dum=p=ListNode()
            while a and b:
                if a.val<=b.val:
                    p.next = a
                    a = a.next
                else:
                    p.next = b
                    b = b.next
                p = p.next
            p.next = a or b
            return dum.next
        
        if not head or not head.next:
            return head
        slow=fast=head
        while fast.next and fast.next.next:
            slow,fast = slow.next,fast.next.next
        a, b = head, slow.next
        slow.next = None
        return merge(self.sortList(a), self.sortList(b))