MergeSort linkedList

MergeSort linkedList.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    
    def findMiddle(self, head):
        slow, fast = head, head
        while fast and fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        return slow
    
    def merge(self, left, right):
        dummy = tail = ListNode()
        p1, p2 = left, right
        
        while p1 and p2:
            if p1.val < p2.val: 
                tail.next = p1
                p1 = p1.next
            else:
                tail.next = p2
                p2 = p2.next
            tail = tail.next
                
        if p1: tail.next = p1
        if p2: tail.next = p2
            
        return dummy.next
    
    
    def sortList(self, head: ListNode) -> ListNode:
        
        if head is None or head.next is None:  return head
        
        middle = self.findMiddle(head)
        rightNode, middle.next = middle.next, None
        
        left = self.sortList(head)
        right = self.sortList(rightNode)
        
        return self.merge(left, right)