Почему это работает
- fast шагает вдвое дальше slow, поэтому, когда fast кончается, slow стоит в конце первой половины: середина найдена без индексов и подсчёта длины.
- slow.next = none превращает половины в два отдельных списка, и каждый сортирует та же функция сама по себе.
- merge каждый раз берёт меньшую голову и перевешивает её за tail; когда один список кончился, остаток другого уже отсортирован и больше, его цепляем одной ссылкой.
Сложность
Время O(n log n): деление пополам даёт log n уровней, и на каждом поиск середин и слияния проходят каждый узел постоянное число раз. Память O(log n): стек вызовов; узлы перевешиваются, а не копируются.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗