Sort List

Средняя№148сортировка слиянием

Дана голова односвязного списка чисел. Нужно отсортировать его по возрастанию и вернуть новую голову, лучше всего за O(n log n). Наш список: 8 → 3 → 5 → 1 — ответ 1 → 3 → 5 → 8.

148 Sort ListРазбор · 1×

Пример: отсортировать связный список 8 → 3 → 5 → 1 слиянием: найти середину через slow и fast, разрезать, отсортировать половины, слить.

8351
ждёт в стеке вызововтекущий вызов или только что прицепленный узелотсортированослитый список, ещё не заполненуже слито наверх

sortList([8, 3, 5, 1]): 4 узла, делим

01/47
сначала · назад · пуск · шаг
Скорость
1function sortList(head):
2 if head is none or head.next is none:
3 return head
4 slow = head
5 fast = head.next
6 while fast is not none and fast.next is not none:
7 slow = slow.next
8 fast = fast.next.next
9 right = slow.next
10 slow.next = none // cut the list after slow
11 left = sortList(head)
12 right = sortList(right)
13 return merge(left, right)
14
15function merge(a, b):
16 tail = dummy // a spare node in front of the result
17 while a and b are not none:
18 link the smaller head behind tail, step on
19 tail.next = whichever of a and b is left
20 return dummy.next
состояние
head
8
slow
–
fast
–
left
–
right
–
a
–
b
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. fast шагает вдвое дальше slow, поэтому, когда fast кончается, slow стоит в конце первой половины: середина найдена без индексов и подсчёта длины.
  2. slow.next = none превращает половины в два отдельных списка, и каждый сортирует та же функция сама по себе.
  3. merge каждый раз берёт меньшую голову и перевешивает её за tail; когда один список кончился, остаток другого уже отсортирован и больше, его цепляем одной ссылкой.

Сложность

Время O(n log n): деление пополам даёт log n уровней, и на каждом поиск середин и слияния проходят каждый узел постоянное число раз. Память O(log n): стек вызовов; узлы перевешиваются, а не копируются.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.