Merge Sort for Linked List in Python

Problem Explanation You are given the head of a linked list . Your task is to sort the linked list using Merge Sort . Example: Input: 40 → 20 → 60 → 10 → 50 → 30 Output: 10 → 20 → 30 → 40 → 50 → 60 Method Used: Merge Sort Idea Merge Sort works in three steps: Divide the linked list into two halves Recursively sort both halves Merge the sorted halves Why This Method? Time complexity: O(n log n) Space complexity: O(1) (no extra arrays) Best sorting algorithm for linked lists Python Code with Explanation class Solution : def mergeSort ( self , head ): Defines the function. if not head or not head . next : return head Base case: If list is empty or has one node → already sorted. mid = self . getMiddle ( head ) Find the middle of the linked list. next_to_mid = mid . next mid . next = None Split the list into two halves. left = self . mergeSort ( head ) Recursively sort the left half. right = self . mergeSort ( next_to_mid ) Recursively sort the right half. sorted_list = self . merge ( left