class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        def helper(h):
            if h is None or h.next is None:
                return h

            r = h
            t = h

            while r.next and r.next.next:
                r=r.next.next
                t=t.next

            h2 = t.next
            t.next = None

            list1 = helper(h)
            list2 = helper(h2)

            sentinel = ListNode()
            ret = sentinel

            while list1 and list2:
                if list1.val <= list2.val:
                    sentinel.next = list1
                    list1 = list1.next
                else:
                    sentinel.next = list2
                    list2 = list2.next
                sentinel = sentinel.next

            while list1:
                sentinel.next = list1
                list1 = list1.next
                sentinel = sentinel.next
            while list2:
                sentinel.next = list2
                list2 = list2.next
                sentinel = sentinel.next

            return ret.next
        return helper(head)