Sort List - Merge Sort on Lists

$1.$ Find the middle node using slow/fast pointers.

$2.$ Split the list into two halves.

$3.$ Recursively sort each half.

$4.$ Merge the sorted halves.

Unlike arrays, splitting a linked list is $O(n)$ but doesn't require extra space. The merge step is also in-place.