You get the head of a singly linked list. Sort the list in ascending order and return the head of the sorted list.
Copying the values into an array and sorting that is easy. Can you relink the nodes themselves in O(n log n) time with only O(1) extra memory? The judge only checks the answer, so that part is up to you.
Equal values both stay in the list, next to each other.
An empty list is already sorted: return null.
Constraints
0 and 5 * 10⁴ nodes.-10⁵ <= Node.val <= 10⁵Merge sort suits linked lists: splitting needs no random access, and merging two sorted lists only relinks nodes, without copying.