Why it works
- fast moves twice as far as slow, so when fast runs out, slow stands at the end of the first half: the middle is found without an index or a count.
- slow.next = none makes the two halves separate lists, so each one is sorted by the same function on its own.
- merge takes the smaller head each time and relinks it behind tail; once one list runs out, the rest of the other is already sorted and larger, so it joins with one link.
Complexity
Time O(n log n): halving gives log n levels, and on each level finding the middles and merging pass every node a constant number of times. Memory O(log n): the call stack; the nodes are relinked, not copied.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗