Как объединить два отсортированных списка на Python: задача LeetCode.

Альбина раскрывает секреты решения задачи, которую она дает на собеседованиях. Суть задачи заключается в том, что нужно объединить два отсортированных списка. На удивление, не все справляются с этим заданием.

#LeetCode #python #АлгоритмическаяКачалка #Программирование #Алгоритмы

[olegbalandin]

Я бы обратил внимание, что при улучшении можно было бы вынести повторяющиеся 4 раза код(где меняются циферки 1-2) в отдельный метод... это бы сэкономило более 17 строк кода... при этом код бы стал более красивым, связным... Но на скорость работы сильно не повлияло бы конечно...

[чжуанцзы-иъ]

Всех смутила структура данных - список) а так, алгоритм рабочий)

[andreys]

Это решается намного проще
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
current = head
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next

current.next = list1 or list2
return head.next

[АлександрТрубников-ож]

А разве не нужно делать проверку на то что и последующие элементы второго списка не больше(не меньше) чем текущее значения первого списка? Прим.:
1, 2, 4
1, 7, 9.
Ведь при то реализации, что показана на видео не будет сортировки, и запишется 1, 2, 7, 4, 9?

[qrthack]

Привет, у меня такой вопрос, коммерческого опыта нет, знаю C, Python, люблю Computer Science. Хочу в backend, выбираю между Java, C#, Golang что посоветуешь, и почему? интересно твое мнение.

[ЕвгенияМамонова-кв]

Я, конечно все понимаю, но в задаче не сказано, что нельзя использовать всю мощь языка Python. Поэтому мне не совсем понятны подобные решения и тем более то, что не каждый мидл может это решить. Можно, конечно писать длинный код, но все решается в 11 строк кода с учетом измерения времени выполнения кода. Может быть я действительно чего-то не понял? Может быть действительно нужен некий изврат и притвориться, что у языка нет встроенных функций для быстрого и качественного решения подобной задачи? Я написал решение с условием, что списки могут быть и не отсортированы. Поправьте меня, если я не прав, пожалуйста

class Solution:
def mergeTwoLists(self, list1, list2):
list3 = list1.copy()
list3.extend(list2)
print(sorted(list3))
# print(list3)

import time

start = time.time()
sol = Solution()
sol.mergeTwoLists(list1 = [1, 2, 4], list2 = [1, 3, 4])

finish = time.time() - start
print(finish)

[незнакомкаёёё]

Чем будет отличаться результат при слиянии списков и сортировке?

[leonid]

Было бы интересно посмотреть на то, как можно улучшить алгоритм, не обязательно даже самому думать, просто посмотреть решения, и объяснить почему это так работает. А то уже в двух роликах вы рассматриваете не самые эффективные алгоритмы.

[qulinxao]

код проще если начальный result - сделать пустым элементом (any, None) тогда при выводе выдаем result.Next
а вообще через условные выражение решается в одну строку:
return list1 if not list2 else list2 if not list1 else ListNode(list1.val, self.mergeTwoLists(list1.next, list2)) if list1.val<=list2.val else self.mergeTwoLists(list2, list1)

[plathardstuck]

Что за собесы где можно обычные питонячьи списки?