leetcode-148 Sort Linked List in O(n logn) time and O(1) memory

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # Split the list into two halves
        left = head
        right = self.get_mid(head)
        # Cut the two parts
        right.next, right = None, right.next
        
        left = self.sortList(left)
        right = self.sortList(right)
        
        return self.merge(left, right)
    

    def get_mid(self, head):
        slow = head
        fast = head.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    

    def merge(self, list1, list2):
        head = tail = ListNode()
        while list1 and list2:
            if list1.val > list2.val:
                tail.next = list2
                list2 = list2.next
            else:
                tail.next = list1
                list1 = list1.next
            tail = tail.next
        
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2
        
        return head.next