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 Explained if not head or not head.next: This is the base cas