Sort List

class Solution:
    def sortList(self, head):
        
        def mergesort(head):
            
            if not head:
                return head
            if not head.next:
                return head

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

            list1 = head
            list2 = slow.next
            slow.next = None

            l1 = mergesort(list1)
            l2 = mergesort(list2)

            result = temp = ListNode(-1, None)
            while l1 or l2:
                l1_val = float('inf') if not l1 else l1.val
                l2_val = float('inf') if not l2 else l2.val
                temp.next = ListNode(min(l1_val, l2_val), None)
                if l1_val > l2_val:
                    l2 = l2.next
                else:
                    l1 = l1.next
                temp = temp.next
            return result.next

        
        return qsort(head)