Sort a Linked List using Merge Sort

Approach:
Step 1 Find middle of linked list
Step 2 Split into two halves
Step 3 Sort both halves
Step 4 Merge two sorted lists

Why this works???
Divide and conquer
smaller lists easier to sort
merge keeps order

Code
class ListNode:
def init(self,val=0,next=None):
self.val=val
self.next=next

def sortList(head):
if not head or not head.next:
return head
slow,fast=head,head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
mid=slow.next
slow.next=None
left=sortList(head)
right=sortList(mid)
return merge(left,right)

def merge(l1,l2):
dummy=ListNode()
curr=dummy
while l1 and l2:
if l1.val<l2.val:
curr.next=l1
l1=l1.next
else:
curr.next=l2
l2=l2.next
curr=curr.next
curr.next=l1 if l1 else l2
return dummy.next

Limitation:
Uses recursion