Sort List

def sortList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    curr = head
    l = 0
    while curr is not None:
        l += 1
        curr = curr.next
    
    return self.mergesort(head, l)
        
def mergesort(self, head, l):
    if head is None or head.next is None:
        return head
    mid = l // 2
    left, lend, right = head, head, head
    for _ in range(mid-1):
        lend = lend.next
        right = right.next
    right = right.next
    lend.next = None
    left = self.sort(left, mid)
    right = self.sort(right, l-mid)
    head = self.merge(left, right)
    return head
        
def sort(self, head, l):
    if head is None or head.next is None:
        return head
    return self.mergesort(head, l)
    
def merge(self, left, right):
    res = ListNode(0)
    tail = res
    while left and right:
        if left.val < right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next
        tail = tail.next
    
    if left:
        tail.next = left
    if right:
        tail.next = right
    
    return res.next