На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: https://leetcode.com/problems/reverse-linked-list
Дан указатель head на начало односвязного списка, необходимо развернуть список и вернуть развернутый список.
1. Решение с использованием массива
Одним из способов решения этой задачи является использование массива для хранения всех узлов списка. После этого мы можем пройтись по массиву в обратном порядке, устанавливая указатели next у каждого узла.
Описание решения
Инициализация массива: Мы создаем пустой массив
nodes, который будем использовать для хранения всех узлов списка.Заполнение массива: Пройдя по всему списку, мы добавляем каждый узел в массив. В результате массив
nodesбудет содержать все узлы в порядке их появления в списке.Перепривязка указателей: Пройдя по массиву слева направо, начиная со второго элемента, мы устанавливаем для каждого узла
nextуказатель на предыдущий элемент в массиве.Обнуление указателя next у первого элемента: Так как первый элемент в массиве (который был последним узлом списка) должен стать последним узлом перевернутого списка, его указатель
nextдолжен быть установлен вNone.Возвращаем новый head: В конце мы возвращаем последний элемент массива как новый
headперевернутого списка.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None: # Если список пуст, возвращаем None
return None
nodes = [] # Массив для хранения узлов
while head:
nodes.append(head) # Добавляем узел в массив
head = head.next # Переходим к следующему узлу
for i in range(1, len(nodes)):
node = nodes[i]
# Устанавливаем указатель next
node.next = nodes[i - 1]
# Устанавливаем None для последнего элемента в перевернутом списке
nodes[0].next = None
return nodes[-1] # Возвращаем новый headСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(n), так как мы сохраняем все элементы списка в массив.
Визуализация
Давайте рассмотрим визуализацию работы алгоритма на примере списка 1 -> 2 -> 3 -> 4 -> 5 -> NULL
-
Инициализация пустого массива nodes:
• Начинаем с пустого массива: nodes = [].
-
Заполнение массива узлами списка:
• Проходим по исходному списку и добавляем каждый узел в массив:
• После первого шага:
nodes = [1](где 1 — это ссылка на узел списка с значением 1)• После второго шага:
nodes = [1, 2]• После третьего шага:
nodes = [1, 2, 3]• После четвертого шага:
nodes = [1, 2, 3, 4]• После пятого шага:
nodes = [1, 2, 3, 4, 5]Теперь массив nodes содержит ссылки на все узлы списка в исходном порядке.
-
Перепривязка указателей next:
• Теперь мы идем по массиву, начиная со второго индекса, и для каждого узла устанавливаем его
nextуказатель на предыдущий узел в массиве.• Для узла 2 (второго элемента массива):
nodes[1].next = nodes[0]Новый список:
2 <-> 1(первый узел все еще ссылается на второй, поэтому связь идет в обе стороны, цикличная связь)• Для узла 3 (третьего элемента массива):
nodes[2].next = nodes[1]Новый список: 3 -> 2 <-> 1
• Для узла 4 (четвертого элемента массива):
nodes[3].next = nodes[2]Новый список:
4 -> 3 -> 2 <-> 1• Для узла 5 (пятого элемента массива):
nodes[4].next = nodes[3]Новый список:
5 -> 4 -> 3 -> 2 <-> 1В этот момент все узлы, начиная со второго, указывают на предыдущие узлы в новом порядке.
-
Обнуление указателя next для первого узла массива:
• Поскольку первый элемент массива теперь последний в новом списке, его next указатель должен быть
None.nodes[0].next = NoneТеперь первый узел (бывший 1 -> NULL) становится последним:
5 -> 4 -> 3 -> 2 -> 1 -> NULL. -
Возвращаем новый head списка:
• Последний элемент массива
nodes[-1], который содержит узел с значением5, теперь становится новымheadсписка.В итоге, исходный список
1 -> 2 -> 3 -> 4 -> 5 -> NULLпревращается в перевернутый список5 -> 4 -> 3 -> 2 -> 1 -> NULL.
2. Решение с использованием метода двух указателей
Подход
Этот алгоритм не требует использования дополнительной памяти, кроме нескольких указателей, что делает его более эффективным по сравнению с методом на основе массива. Идея состоит в том, чтобы постепенно развернуть связи между узлами, проходя по списку один раз.
Алгоритм
Инициализация указателя prev:
Мы начинаем с указателя prev, который изначально равенNone. Этот указатель будет использоваться для хранения предыдущего узла в перевернутом списке.-
Проход по списку:
Мы проходим по списку, изменяя указатели next каждого узла, чтобы они указывали на предыдущий узел (
prev). Для этого в цикле мы выполняем следующие шаги:• Сохраняем указатель на следующий узел (
tmp = head.next), чтобы не потерять его после измененияhead.next.• Изменяем текущий указатель
nextузлаhead, чтобы он указывал наprev.• Перемещаем
prevна текущий узел (prev = head).• Перемещаем
headна следующий узел (head = tmp). -
Возвращаем новый head:
После завершения прохода по списку
prevбудет указывать на последний узел исходного списка, который теперь станетheadперевернутого списка.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None # Инициализация указателя на предыдущий узел
while head:
tmp = head.next # Сохраняем указатель на следующий узел
head.next = prev # Разворачиваем текущий узел
prev = head # Смещаем указатель prev на текущий узел
head = tmp # Переходим к следующему узлу
return prev # Возвращаем новый head спискаСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(1), так как используем только два указателя.
Визуализация
Рассмотрим исходный список 1 -> 2 -> 3 -> 4 -> 5 -> NULL.
-
Инициализация:
prev = None,head = 1. -
Первый шаг цикла:
•
tmp = 2(сохраняем следующий узел)•
head.next = None(разворачиваем указатель1 -> NULL)•
prev = 1,head = 2.Состояние: 1 -> NULL, 2 -> 3 -> 4 -> 5 -> NULL.
-
Второй шаг цикла:
•
tmp = 3(сохраняем следующий узел)•
head.next = 1(разворачиваем указатель2 -> 1)•
prev = 2,head = 3.Состояние:
2 -> 1 -> NULL,3 -> 4 -> 5 -> NULL. -
Повторяем до конца:
После завершения всех шагов получаем перевернутый список:
5 -> 4 -> 3 -> 2 -> 1 -> NULL.
Комментарии (20)
datacompboy
24.08.2024 13:41А где векторизация? Где тестирование на терабайтных списках?....
https://habr.com/ru/articles/682332/ & https://habr.com/ru/articles/688874/
nickolaym
24.08.2024 13:41Первое и самое главное: этическая сторона дела. Задача на интервью предназначена для проверки самостоятельного мышления соискателя. Выкладывать её успешное решение на всеобщий обзор - это вносить смещение в объективность следующих интервью. Проще говоря: автор выложил спойлер.
Сама по себе задача очень простая (на литкоде имеет уровень easy). Это значит, что обсуждать её есть смысл, когда есть что добавить интересного к эталонному решению. Ну вот выше уже упомянули про терабайтные наборы. Или, например, обсудить существенно разные реализации (в существенно разных языках - или в разных парадигмах на одном и том же питоне). Или ещё что-нибудь... Иначе это как-то не соответствует заявленному автором званию Senior.
Уже сам по себе старт: "давайте сделаем дефолтную реализацию с O(n) дополнительной памяти, а потом разгоним" выглядит странно. Ну ок, тогда давайте поиграем в другой жанр, в ненормальное программирование: найти самый медленный и прожорливый алгоритм? Есть же соревнование в замедлении сортировки, почему бы и в замедление разворота списка не посоревноваться?
В общем, решение на пятёрочку, а статья на двоечку с плюсом. За это и минусы. А не за мифические обидки.
idsulik Автор
24.08.2024 13:41Окей
Мне когда-то попалась эта задача и я не знал как решить, теперь решил рассказать другим как это сделать, визуальное объяснение, каждому подойдет свой вариант подачи материала, надеюсь моя подача тоже будет полезна кому-то. Причем тут мое звание Senior? Где в задаче это упоминается?) Если я Senior, то должен объяснять только hard задачи? Не вижу логики
Если странно, предложите идею как сделать лучше
Я не про минус на статью писал, а про минус на каждый мой коммент) Если подскажете как сделать статью лучше, пишите. Не про террабайты, а именно эту задачу с ограничениями из литкода
nickolaym
24.08.2024 13:41Просто покажу, как можно на ровном месте сделать чуть красивее.
def revert_sequential_and_verbose(head): prev = None while head: tmp = head.next head.next = prev prev = head head = tmp return prev def revert_using_tuple_assign(head): prev = None while head: head, prev, head.next = head.next, head, prev return prevА можно чуть изощрённее, - избавиться от цикла while на верхнем уровне
def iterate_single_linked(head): while head: ##################### # здесь был спойлер # ##################### def revert_using_for_loop(head): prev = None for curr in iterate_single_linked(head): curr.next, prev = prev, curr return prev def revert_using_reduce(head): def op(prev, curr): ##################### # здесь был спойлер # ##################### return functools.reduce(op, iterate_single_linked(head), None)Разумеется, использование генераторов и ФВП (и даже кортежей) на питоне вносит лишние накладные расходы по сравнению с наивным строго последовательным "сишно-фортрановым" решением. Но, тем не менее...
Вот, что мы бы тут ожидали увидеть на хабре от автора.
idsulik Автор
24.08.2024 13:41Суть статьи ведь показать как решить просто и как решить оптимально, максимально доступным способом, не было цели показать изощренный вариант решения.
Если вы знаете как решить лучше - отлично, объясните данное решение, напишите статью, чтобы другие могли понять плюсы и минусы, вуаля
SpiderEkb
24.08.2024 13:41// head -> node1 -> node2 -> node3 -> nullptr reverseList(Node* head) { // это будет это будет нового списка // newHead = head Node* newHead = head; // следующий после головного узел // headNext = node1 Node* headNext = head->next; // временная переменная Node* tmp; // этот узел будет последним с развернутом списке // head -> nullptr head->next = nullptr; while (headNext != nullptr) { // запомним указатель "через узел" // 1 tmp = node2 // 2 tmp = node3 // 3 tmp = nullptr tmp = headNext->next; // прицепляем головной узел к следующему за ним // 1 node1 -> head -> nullptr // 2 node2 -> node1 -> head -> nullptr // 3 node3 -> node2 -> node1 -> head -> nullptr headNext->next = newHead; // делаем следующий после начала узел "головным" // 1 newHead = node1 // 2 newHead = node2 // 3 newHead = node3 newHead = headNext; // теперь то, что было "через узел", становится следующим // 1 headNext = node2 // 2 headNext = node3 // 3 headNext = nullptr headNext = tmp; }; return newHead; }Тоже самое на С. Тут комментариев больше чем кода. Просто. Оптимально. Минимум накладных расходов. Минимум кода (больше комментариев).
Все это решается в голове. Просто представляете что у вас есть картонные квадратики с номером узла и стрелочкой, выстроенные в определенном порядке (по стрелочкам). И начинаете их двигать так, чтобы порядок поменялся на противоположный.
P.S. до этого такую задачу не решал, написал первое, что в голову пришло пока читал. Потом уже увидел что такое решение уже было предложено.
P.P.S. сама по себе задача бессмысленная. Если вам нужно ходить по списку туда-сюда - есть двусвязные списки. С необходимостью разворачивать односвязный список за 30+ лет практики не сталкивался ни разу. Хотя со списками приходилось работать много в самых разных их реализациях.
idsulik Автор
24.08.2024 13:41+1И к чему вы это?) вы смогли решить это, круто, но есть тысячи других, кто не смог и им нужна помощь, среди них был и я когда-то.
Но на хабре всегда думают, что все всё знают)) ну или думаю, что если они знают, то не надо писать об этом для другихSpiderEkb
24.08.2024 13:41Если хотите помочь - ну предлагайте действительно хорошее решение. А не вот это вот с массивами.
Просто представьте, что вам надо развернуть список из 10 000 000 элементов...
Два поста с оптимальным (по простоте и эффективности) решением - оба с минусами.
idsulik Автор
24.08.2024 13:41+1там ведь два решения, один с массивом, а другой оптимальный, что не нравится?
мое второе решение даже проще, чем то, что вы написали выше
Ощущение, что прочли половину статьи и решили выплеснуть свое недовольство)
Либо даете аргументированный фидбек, либо пишете свою статью с блэк-джеком и шлюхами, все просто)
idsulik Автор
Буду благодарен за обратную связь, критика приветствуется, желательно аргументированная!)
bromzh
Сколько раз в кодовой базе Avito разворачивается список (примерно)? Насколько часто в рабочих задачах приходится его развернуть? Вы используете какую-то библиотеку для этого, или самописное решение?
vvviperrr
лучше бы проверяли, сможет ли кандидат изменить размер процента от продажи товара на площадке. еще ценится умение отписаться от клиента, если товар потерян доставкой. а не вот это вот все.
idsulik Автор
сарказм?)
idsulik Автор
Мне эту задачу давалю на интервью, используют ли они это на деле - вряд ли)