💡Задача: Сортировочный список

Условие: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания

Пример:

Ввод: head = [4,2,1,3]
Вывод: [1,2,3,4]

Ввод: head = [-1,5,3,4,0]
Вывод: [-1,0,3,4,5]

Можете ли вы отсортировать связанный список за O (n logn) времени и O(1) памяти (т.е. постоянного пространства)?

Решение:

class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
arr, itr = [], head

while itr:
arr.append(itr.val)
itr = itr.next
arr.sort() # sort it
itr, i = head, 0
while itr:

itr.val = arr[i]
i += 1
itr = itr.next
return head

Пишите свое решение в комментариях👇

@python_job_interview