Merge Sort for Linked List

#Merge sort for the linked List
class Solution:

    def _len(self, head):
        ans = 0
        while head:
            head = head.next
            ans += 1
        return ans

    def find_mid(self, head):
        half = self._len(head) // 2
        if half > 0:
            half -= 1  # reducing half by one so it send just before the middle

        mid = head
        while half > 0:
            mid = mid.next
            half -= 1

        return mid

    def merge(self, head, mid):

        if not head:
            return mid
        if not mid:
            return head

        if head.val < mid.val:
            root = ListNode(head.val)
            head = head.next
        else:
            root = ListNode(mid.val)
            mid = mid.next

        cur = root

        while head and mid:
            if head.val < mid.val:
                cur.next = ListNode(head.val)
                head = head.next
            else:
                cur.next = ListNode(mid.val)
                mid = mid.next

            cur = cur.next

        while head:
            cur.next = ListNode(head.val)
            head = head.next
            cur = cur.next

        while mid:
            cur.next = ListNode(mid.val)
            mid = mid.next
            cur = cur.next

        return root

    def mergesort(self, head):

        if not head.next:  # If only one node, return the node
            return head

        temp = self.find_mid(head)  # temp is having node just before mid node so that we can break

        mid = temp.next  # mid node
        temp.next = None  # breaking the linked list into two halves

        head = self.mergesort(head)
        mid = self.mergesort(mid)

        ans = self.merge(head, mid)
        return ans

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