[Python手撕]排序链表

# 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: Optional[ListNode]) -> Optional[ListNode]:

        def findmid(head):
            dummy = ListNode(-1)
            dummy.next = head

            fast = dummy
            slow = dummy

            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next

            t = slow
            slow = slow.next
            t.next = None

            return slow
        
        def merge(head1,head2):
            if not head1 and not head2:
                return None
            if not head1:
                return head2
            if not head2:
                return head1
            if head1 and head2:
                cur1 = head1
                cur2 = head2

                dummy = ListNode(-1)
                tail = dummy

                while cur1 and cur2:
                    if cur1.val<=cur2.val:
                        tail.next = cur1
                        cur1 = cur1.next
                        tail = tail.next
                        tail.next = None
                    else:
                        tail.next = cur2
                        cur2 = cur2.next
                        tail = tail.next
                        tail.next = None
            if cur1:
                tail.next = cur1
            if cur2:
                tail.next = cur2
            
            return dummy.next
        
        def sort(head):
            if not head or not head.next:
                return head
            else:
                mid = findmid(head)
                return merge(sort(head),sort(mid))
        
        return sort(head)