@@СуренПетросян-ц5ю по условиям задачи нельзя, так как нужно сделать за O(log(n)), а прохождение по всему списку это O(n), что уже больше. Плюс сортировка O(n*log(n)) Даже если делать слияние, а не сортировку, всё равно O(n), что не подходит. Поэтому и сложная задача
Как вариант, решение через рекурсию: 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
Интересное решение! Думаю, такое тоже могут спросить на собесе, но уверен быть не могу. По связанным спискам мы обязательно посмотрим ещё и на рекурсию. Мне такое решение кажется сложнее. И, наверное, в случае с рекурсией у нас будет `O(n)` по памяти, так как для каждого рекурсивного вызова будет увеличиваться стек
Добрый день! Подскажите пожалуйста как вывести результат в Пайчарме? Я копирую код с решением себе в pycharm, но запустить никак не получается в интернете везде обрубленное решение.
Почему так? А вы проверили такой код? Можно же прямо там на литкод добавить тест кейс и проверить. Не вижу причин чтобы была такая ошибка, там же на каждой итерации новая проверка, какое значение меньше.
@@SurenKhorenyan Большое спасибо за ответ! Разберусь! И ещё если можно вопрос по другой задаче, 27 Remove element. Я не нашел у вас ролика про неё. Выглядит вообще элементарно, удалить из списка те элементы, которые равны определённому значению. Ну прям вообще выглядит простейше - идешь циклом по списку, проверяешь каждый элемент и затем удаляешь через pop(), указывая явно индекс. Или тут в чем-то подвох? Выглядит слишком лёгким даже для уровня Изи
@@andrejkiseljev1600 ознакомлюсь, но я бы не делал через pop, это дорогая операция для списка. Посмотрю, мб лучше просто новый список сделать, а может быть есть ещё какой-то подвох. Ну или правда такая простая задача
@@andrejkiseljev1600 посмотрел, там смысл в том, чтобы менять in-place. Я бы шёл с двумя указателями и менял местами, в самый конец ставил бы лишнее, там в итоге надо вернуть длину готового. Не страшно, что лишнее останется в списке. Надо будет разобрать на канале, спасибо
@@rosseti8767 dummy через next ссылается на следующий элемент. Изначально tail.next смотрит туда же. Сначала мы на tail.next вешаем следующий объект, и он же остаётся на dummy.next. и в итоге там у нас голова нового списка
@@SurenKhorenyan А как dummy находит следующий объект, если он изначально является пустым объектом, в котором указатель на следующий объект = None. Откуда у него появляется указатель на следующий, если непосредственно с dummy мы не взаимодействуем, а только с tail?
@@rosseti8767 тут важно учитывать изменяемость объектов. Если d = TreeNode() и t = d, то они ссылаются на один экземпляр. Поэтому если сделать t.next = [новый объект], то на d.next будет ссылка точно туда же. Это основы ООП
Вариант через создание и сортировку обычного листа получается веселее: 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
Дорого, ведь сортировка по сложности O(n * log n), где n это общая длина обеих коллекций.А в показанном решении O(n), так как мы проходим только один раз Нам же как раз помогают тем, что обе коллекции уже отсортированы Но, возможно, на собеседовании ваш вариант тоже пройдет 😅
@@SurenKhorenyan Ок, спасибо, учту. Я пока только знакомлюсь с алгоритмами - литкод оценил решение 99/84. Подобное как у вас я тоже делал, но видимо где то ошибся с ограничителями, тк сложно поймать, чтобы list1.val не указывал на пустой хвост и выдавал ошибку.
нельзя ли с помощью extend добавить и отсортировать по возрастанию ?
@@СуренПетросян-ц5ю по условиям задачи нельзя, так как нужно сделать за O(log(n)), а прохождение по всему списку это O(n), что уже больше. Плюс сортировка O(n*log(n))
Даже если делать слияние, а не сортировку, всё равно O(n), что не подходит. Поэтому и сложная задача
Как вариант, решение через рекурсию:
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
Интересное решение! Думаю, такое тоже могут спросить на собесе, но уверен быть не могу. По связанным спискам мы обязательно посмотрим ещё и на рекурсию. Мне такое решение кажется сложнее. И, наверное, в случае с рекурсией у нас будет `O(n)` по памяти, так как для каждого рекурсивного вызова будет увеличиваться стек
Добрый день! Подскажите пожалуйста как вывести результат в Пайчарме? Я копирую код с решением себе в pycharm, но запустить никак не получается в интернете везде обрубленное решение.
Если есть ссылка на такое решение пожалуйста скиньте
как я понял нужно сделать обход , где началом будем дамми и пока дамми.вал не равно none
Здравствуйте. Вы имеете в виду как это протестировать у себя на компе? Надо свою обретку добавить.
Это самому делать
а как быть, если списки выглядят например так
[1, 3, 99, 100]
[1, 2, 2, 5]
по вашему коду он схлопнется в итоговый [1, 1, 2, 3, 2, 99, 5, 100]
Почему так? А вы проверили такой код? Можно же прямо там на литкод добавить тест кейс и проверить. Не вижу причин чтобы была такая ошибка, там же на каждой итерации новая проверка, какое значение меньше.
@@SurenKhorenyan Большое спасибо за ответ! Разберусь!
И ещё если можно вопрос по другой задаче, 27 Remove element.
Я не нашел у вас ролика про неё. Выглядит вообще элементарно, удалить из списка те элементы, которые равны определённому значению. Ну прям вообще выглядит простейше - идешь циклом по списку, проверяешь каждый элемент и затем удаляешь через pop(), указывая явно индекс. Или тут в чем-то подвох? Выглядит слишком лёгким даже для уровня Изи
@@andrejkiseljev1600 ознакомлюсь, но я бы не делал через pop, это дорогая операция для списка. Посмотрю, мб лучше просто новый список сделать, а может быть есть ещё какой-то подвох.
Ну или правда такая простая задача
@@andrejkiseljev1600 посмотрел, там смысл в том, чтобы менять in-place. Я бы шёл с двумя указателями и менял местами, в самый конец ставил бы лишнее, там в итоге надо вернуть длину готового. Не страшно, что лишнее останется в списке.
Надо будет разобрать на канале, спасибо
не могу понять как мы работаем все время с одной переменной(хвост) а по факту в ответ даем дамми , хотя с ним ничо не делали
На 5:34 делаем на него ссылку, а ссылка связана с ним напрямую
@@SurenKhorenyan А как у нас взаимодействиями с tail произошли изменения в dummy, то есть при каждом действии с tail меняется и dummy?
@@rosseti8767 dummy через next ссылается на следующий элемент. Изначально tail.next смотрит туда же. Сначала мы на tail.next вешаем следующий объект, и он же остаётся на dummy.next. и в итоге там у нас голова нового списка
@@SurenKhorenyan А как dummy находит следующий объект, если он изначально является пустым объектом, в котором указатель на следующий объект = None. Откуда у него появляется указатель на следующий, если непосредственно с dummy мы не взаимодействуем, а только с tail?
@@rosseti8767 тут важно учитывать изменяемость объектов. Если d = TreeNode() и t = d, то они ссылаются на один экземпляр. Поэтому если сделать t.next = [новый объект], то на d.next будет ссылка точно туда же. Это основы ООП
Супер,жги! То что надо!!!! 🤘🤘🤘🤘💥💥💥💥🤝🤝🤝🥳
Спасибо большое! Рад трудиться ☺
Вариант через создание и сортировку обычного листа получается веселее:
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
Дорого, ведь сортировка по сложности O(n * log n), где n это общая длина обеих коллекций.А в показанном решении O(n), так как мы проходим только один раз
Нам же как раз помогают тем, что обе коллекции уже отсортированы
Но, возможно, на собеседовании ваш вариант тоже пройдет 😅
@@SurenKhorenyan Ок, спасибо, учту. Я пока только знакомлюсь с алгоритмами - литкод оценил решение 99/84. Подобное как у вас я тоже делал, но видимо где то ошибся с ограничителями, тк сложно поймать, чтобы list1.val не указывал на пустой хвост и выдавал ошибку.
@@СтаниславУдалых-у7л главное не останавливаться 😊