MergeSort - Linked List

mergeSort.py

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
class MergeSort:
    def __init__(self, head: ListNode):
        self.head = None
        
    def sortList(self, head: ListNode):
        return self.mergeSort(head)

    def split(self, head: ListNode):
        tail = head
        mid  = head
        cnt  = 0

        while tail != None:
            tail = tail.next

            if cnt % 2 == 0 and cnt > 0:
                mid = mid.next
            cnt += 1

        back     = mid.next
        mid.next = None

        return head, back

    def sortMerge(self, l1: ListNode, l2: ListNode):
        l3  = ListNode(0)
        out = l3

        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                l3.next = ListNode(l1.val)
                l1 = l1.next
                l3 = l3.next
            else:
                l3.next = ListNode(l2.val)
                l2 = l2.next
                l3 = l3.next

        while l1 != None:
            l3.next = ListNode(l1.val)
            l1 = l1.next
            l3 = l3.next

        while l2 != None:
            l3.next = ListNode(l2.val)
            l2 = l2.next
            l3 = l3.next

        return out.next

    def mergeSort(self, node: ListNode):
        if node == None or node.next == None:
            return node

        front, back = self.split(node)
        front = self.mergeSort(front)
        back  = self.mergeSort(back)

        return self.sortMerge(front, back)