Sort a Linked List using Merge Sort

Sorting a Linked List Using Merge Sort Problem You’re given the head of a linked list and asked to sort it using merge sort. Strategy I didn’t try to sort the list directly. That just made it confusing. Instead, I broke it down into smaller steps: Find the middle of the list Split it into two halves Sort each half Merge them back together So it’s really just: split ,sort , merge Code class Solution : def mergeSort ( self , head ): if not head or not head . next : return head slow = head fast = head prev = None while fast and fast . next : prev = slow slow = slow . next fast = fast . next . next prev . next = None left = self . mergeSort ( head ) right = self . mergeSort ( slow ) return self . merge ( left , right ) def merge ( self , l1 , l2 ): dummy = Node ( 0 ) current = dummy while l1 and l2 : if l1 . data < l2 . data : current . next = l1 l1 = l1 . next else : current . next = l2 l2 = l2 . next current = current . next current . next = l1 if l1 else l2 return dummy . next Key Lines