153: Sort linked list

Дан связный список, верните отсортированный связный список. Сортировка должна работать за O(nlogn)

 

Пример 1

Input:  2 -> 3 -> 1

Output: 1 -> 2 -> 3

Пример 2

Input:  3 -> 2 -> 1

Output: 1 -> 2 -> 3