Merge Sort for Linked List

Hi everyone! Today I worked on sorting a linked list using Merge Sort . Unlike arrays, we can’t directly apply quick access techniques, so merge sort works best here. Problem Given a linked list, sort it using merge sort . Example: Input: 10 -> 50 -> 30 -> 20 Output: 10 -> 20 -> 30 -> 50 My Approach Sorting a linked list is tricky because: No random access (like arrays) Need efficient splitting and merging So I used: > Merge Sort (Divide & Conquer) Logic Find middle of list using slow & fast pointers Split the list into two halves Recursively sort both halves Merge the sorted halves Code (Python) class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self, head): slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next return slow def merge(self, l