MERGE SORT ON A LINKED LIST

How I Understood Merge Sort on a Linked List When I first saw this problem, I knew merge sort works for arrays, but I wasn’t sure how to apply it to linked lists. After breaking it down, I realized merge sort is perfect for linked lists because we can split and merge efficiently without extra space for indexing. ** Problem** Given the head of a singly linked list, sort the list using merge sort and return the sorted head. Example: Python Input: 4 -> 2 -> 1 -> 3 -> None Output: 1 -> 2 -> 3 -> 4 -> None What I Noticed Key observations: Linked lists cannot access middle by index, so we use slow and fast pointers to find the middle Merge sort works in divide and conquer manner: Divide list into two halves Recursively sort each half Merge the sorted halves Merging two sorted linked lists is efficient and done in-place. ** What Helped Me** Breaking down the solution into three main steps: Find the middle: Use slow and fast pointers Recursively sort halves: Split at middle and call mergeSort