Merge Two Sorted Lists | Решение на Python | LeetCode 21

Решение LeetCode задачи "21. Merge Two Sorted Lists"
Задача на LeetCode: leetcode.com/problems/merge-t...
Код с решением тут: github.com/mahenzon/leetcode-...
Паблик в ВК: SurenKhorenyan
Канал в Telegram: t.me/Khorenyan
Метки:
00:00 Начало
01:36 Рисование
03:32 Код
8:42 Случайные числа и итог

[@lifestyletv139]

Супер,жги! То что надо!!!! 🤘🤘🤘🤘💥💥💥💥🤝🤝🤝🥳

[@SurenKhorenyan]

Спасибо большое! Рад трудиться ☺

[@0x12th]

Как вариант, решение через рекурсию:
if not list1:
return list2
if not list2:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2

[@SurenKhorenyan]

Интересное решение! Думаю, такое тоже могут спросить на собесе, но уверен быть не могу. По связанным спискам мы обязательно посмотрим ещё и на рекурсию. Мне такое решение кажется сложнее. И, наверное, в случае с рекурсией у нас будет `O(n)` по памяти, так как для каждого рекурсивного вызова будет увеличиваться стек

[@user-kj4pn2nk1v]

Вариант через создание и сортировку обычного листа получается веселее:
list3 = []
while list1 is not None:
list3.append(list1.val)
list1 = list1.next
while list2 is not None:
list3.append(list2.val)
list2 = list2.next
list3.sort()
result = dummy = ListNode()
for i in list3:
result.next = ListNode(i)
result = result.next
return dummy.next

[@SurenKhorenyan]

Дорого, ведь сортировка по сложности O(n * log n), где n это общая длина обеих коллекций.А в показанном решении O(n), так как мы проходим только один раз
Нам же как раз помогают тем, что обе коллекции уже отсортированы
Но, возможно, на собеседовании ваш вариант тоже пройдет 😅

[@user-kj4pn2nk1v]

​@@SurenKhorenyan Ок, спасибо, учту. Я пока только знакомлюсь с алгоритмами - литкод оценил решение 99/84. Подобное как у вас я тоже делал, но видимо где то ошибся с ограничителями, тк сложно поймать, чтобы list1.val не указывал на пустой хвост и выдавал ошибку.

[@SurenKhorenyan]

@@user-kj4pn2nk1v главное не останавливаться 😊

[@andrejkiseljev1600]

а как быть, если списки выглядят например так
[1, 3, 99, 100]
[1, 2, 2, 5]
по вашему коду он схлопнется в итоговый [1, 1, 2, 3, 2, 99, 5, 100]

[@SurenKhorenyan]

Почему так? А вы проверили такой код? Можно же прямо там на литкод добавить тест кейс и проверить. Не вижу причин чтобы была такая ошибка, там же на каждой итерации новая проверка, какое значение меньше.

[@andrejkiseljev1600]

​@@SurenKhorenyan Большое спасибо за ответ! Разберусь!
И ещё если можно вопрос по другой задаче, 27 Remove element.
Я не нашел у вас ролика про неё. Выглядит вообще элементарно, удалить из списка те элементы, которые равны определённому значению. Ну прям вообще выглядит простейше - идешь циклом по списку, проверяешь каждый элемент и затем удаляешь через pop(), указывая явно индекс. Или тут в чем-то подвох? Выглядит слишком лёгким даже для уровня Изи

[@SurenKhorenyan]

@@andrejkiseljev1600 ознакомлюсь, но я бы не делал через pop, это дорогая операция для списка. Посмотрю, мб лучше просто новый список сделать, а может быть есть ещё какой-то подвох.
Ну или правда такая простая задача

[@SurenKhorenyan]

@@andrejkiseljev1600 посмотрел, там смысл в том, чтобы менять in-place. Я бы шёл с двумя указателями и менял местами, в самый конец ставил бы лишнее, там в итоге надо вернуть длину готового. Не страшно, что лишнее останется в списке.
Надо будет разобрать на канале, спасибо

[@user-xu5pp7lk5g]

Добрый день! Подскажите пожалуйста как вывести результат в Пайчарме? Я копирую код с решением себе в pycharm, но запустить никак не получается в интернете везде обрубленное решение.

[@user-xu5pp7lk5g]

Если есть ссылка на такое решение пожалуйста скиньте

[@danilbanan406]

как я понял нужно сделать обход , где началом будем дамми и пока дамми.вал не равно none

[@SurenKhorenyan]

Здравствуйте. Вы имеете в виду как это протестировать у себя на компе? Надо свою обретку добавить.
Это самому делать

[@danilbanan406]

не могу понять как мы работаем все время с одной переменной(хвост) а по факту в ответ даем дамми , хотя с ним ничо не делали

[@SurenKhorenyan]

На 5:34 делаем на него ссылку, а ссылка связана с ним напрямую

[@rosseti8767]

@@SurenKhorenyan А как у нас взаимодействиями с tail произошли изменения в dummy, то есть при каждом действии с tail меняется и dummy?

[@SurenKhorenyan]

@@rosseti8767 dummy через next ссылается на следующий элемент. Изначально tail.next смотрит туда же. Сначала мы на tail.next вешаем следующий объект, и он же остаётся на dummy.next. и в итоге там у нас голова нового списка

[@rosseti8767]

@@SurenKhorenyan А как dummy находит следующий объект, если он изначально является пустым объектом, в котором указатель на следующий объект = None. Откуда у него появляется указатель на следующий, если непосредственно с dummy мы не взаимодействуем, а только с tail?

[@SurenKhorenyan]

@@rosseti8767 тут важно учитывать изменяемость объектов. Если d = TreeNode() и t = d, то они ссылаются на один экземпляр. Поэтому если сделать t.next = [новый объект], то на d.next будет ссылка точно туда же. Это основы ООП