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

[@Alcoholdehydrogenas]

Ничего не понял, но очень интересно

[@olegbalandin6856]

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

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

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

[@andreysergeev5916]

Это решается намного проще
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

[@supreltd]

так же решил, только при проверке на наличие элементов в списке после цикла, использовал тернарник.

[@qrthack]

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

[@Boatengn1prince]

Если ты еще не пошел в дворники, то выбор очень прост. Посмотри и проанализируй рынок

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

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

[@romanvolkov4296]

Тем, что time complexity сортировки в среднем O(NlogN), а код из видео выполняется за О(N)

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

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

[@designed6102]

Не досмотрел ещё видос, но по-сути нормальный алгоритм должен двигать курсор дальше и опять проверять меньше ли первый элемент чем второй

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

Я, конечно все понимаю, но в задаче не сказано, что нельзя использовать всю мощь языка 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)

[@ДмитрийЖучков-щ8н]

Слияние уже сортированных списков по сложности проще чем сортировка одного общего списка. Задача именно так поставлена, а если не обращать внимание на отдельные слова в постановке, то зачем браться за решение :)

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

@@ДмитрийЖучков-щ8н в моем коде нет разницы, сортирован список, или нет. Результат будет одинаков

[@romanvolkov4296]

Начнем с того, что в задаче - LinkedList, а не простой массив, и ты тупо не можешь его скопировать, объединить и отсортировать таким способом, закончим тем, что твое решение выполняется за N log N времени, и если тестировать не на списках из 3 элементов, то разница большая

[@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

[@leonid1753]

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

[@PythonHedgehog]

Это учебные алгоритмы для совсем зеленых.
Если интересно посмотреть что-то посложнее, то поищите в интернете алгоритм timsort например.

[@RaptorT1V]

@@PythonHedgehog кста, именно timsort работает под капотом у sorted() в Python

[@plathardstuck28]

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

[@technokratosTV]

Мы и сами в шоке, как так получается. Обычно в качестве ответа мы видим вот это:
return sorted(list1 + list2)
🤷‍♂️🤷‍♂️

[@hey-rg9lk]

ну наверно если ты проходишь собеседование на позицию питониста, то задачки будешь решать на питоне и пользоваться структурами и алгоритмами которые тебе предоставил язык?

[@plathardstuck28]

@@hey-rg9lk
Никто щас на собесах не спрашивает за списки и даже за deque , потому, что подразумевается что кандидат уже освоил это всё. Спрашивают односвязный список, бинарные деревья, графы и тому подобные вещи. Если приходится использовать встроенные списки, то задача про что-то более сложное (матрица, треугольник паскаля) и подразумевает что ты умеешь работать со списками на уровне сортировки значений.

[@plathardstuck28]

@@technokratosTV может меня на собес позовёте? ;) я правда только 4 месяца учусь и не освоил такие вещи как докер, рэббит и т.п., но в базовые алгоритмы типа сортировки слиянием и пузырьком, просчёта бинарных деревьев умею :)

[@hey-rg9lk]

@@plathardstuck28 в том то и дело что linked list кроме как алгоритмических задач нигде не будет использоваться в боевых решениях) а если обходить те же деревья или графы, мы снова приходим к тому что нужно использовать очереди