Given the head of a singly linked list, sort it in non-decreasing order and return the sorted list's head. Because a linked list can't be randomly indexed the way an array can, most in-place sorting algorithms don't translate directly. Merge sortMerge Sort on a Linked ListA divide-and-conquer sort: split the list into two halves (using slow/fast pointers to find an even split point), recursively sort each half, then merge the two sorted halves back together. Unlike merge sort on an array, no auxiliary array is ever needed — splitting only cuts a link, and merging only re-links existing nodes. is the exception — it only ever needs sequential access, both to split the list (find a midpoint, cut the link) and to merge two already-sorted halves (walk both with two pointers, re-linking as you go, exactly like merging two sorted lists). That makes it a natural fit for a linked list, running in O(n log n) time using only O(log n) extra space for the recursion.