💡Задача: Сортировочный список
Условие: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания
Пример:
Ввод: 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
Условие: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания
Пример:
Ввод: 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) памяти (т.е. постоянного пространства)?
Решение:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
arr, itr = [], head
while itr:
arr.append(itr.val)
itr =
arr.sort() # sort it
itr, i = head, 0
while itr:
itr.val = arr[i]
i += 1
itr =
return head
Пишите свое решение в комментариях👇
@python_job_interview