На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: https://leetcode.com/problems/middle-of-the-linked-list
Дан указатель head на начало односвязного списка, нужно вернуть средний узел списка.
Если средних узлов два, нужно вернуть второй средний узел.
1. Решение с использованием массива
Подход
Преобразование списка в массив упрощает доступ к элементам по индексу. Мы проходим по списку и сохраняем все узлы в массив, так как доступ по индексу в массиве осуществляется за постоянное время O(1). После этого мы легко можем найти средний элемент, просто взяв элемент по индексу len(items) // 2
Алгоритм
Пройти по списку и сохранить все его элементы в массив.
Определить индекс среднего элемента массива.
Вернуть элемент, находящийся по этому индексу.
Код решения
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
items = []
while head: #None
items.append(head)
head = head.next
return items[len(items) // 2]Сложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(n), так как мы сохраняем все элементы списка в массив.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5Массив после прохождения по списку:
[1, 2, 3, 4, 5]Индекс среднего элемента:
5 // 2 = 2Средний элемент в массиве: 3
0 1 2 3 4
[1, 2, {3}, 4, 5]
2. Решение с подсчетом длины списка
Подход
В этом подходе мы сначала считаем количество элементов в списке, чтобы точно знать, сколько узлов в нем содержится. Считая количество узлов, мы можем определить индекс среднего элемента как length // 2. Затем, проходя список во второй раз, мы останавливаемся на этом индексе и возвращаем соответствующий узел.
Алгоритм
Пройти по списку и подсчитать количество элементов.
Пройти по списку снова до среднего элемента и вернуть его.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
count = self.count(head)
for _ in range(count // 2):
head = head.next
return head
def count(self, head):
res = 0
while head:
res += 1
head = head.next
return resСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(1), так как мы не используем дополнительную память.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5-
Проход 1: Подсчет длины списка
• Длина списка:
5 Средний индекс:
5 // 2 = 2-
Проход 2: Получение среднего элемента
• Проходим через узлы до индекса, который мы вычислили на 3 шаге:
1 (0), 2 (1), 3 (2) Средний элемент: 3
3. Решение с использованием метода быстрого и медленного указателя
Подход
Этот метод использует два указателя: быстрый и медленный. Быстрый указатель движется по два узла за раз, а медленный - по одному. Когда быстрый указатель достигает конца списка или выходит за пределы списка, медленный находится на середине. Это происходит потому, что быстрый указатель проходит вдвое больше узлов за одно и то же время. Этот метод эффективен, так как требует только одного прохода по списку и использует минимальное дополнительное пространство.
Алгоритм
Инициализировать два указателя, быстрый и медленный, которые указывают на начало списка.
Перемещать медленный указатель на один шаг, а быстрый на два шага, пока быстрый указатель не достигнет конца списка.
Когда быстрый указатель достигнет конца списка или выходит за его пределы, медленный указатель будет находиться на среднем элементе.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(1), так как используем только два указателя.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5-
Начальное положение:
• Медленный указатель (S) на 1
• Быстрый указатель (F) на 1
-
Шаг 1:
•
S: 2(двигается на 1 узел вперед)•
F: 3(двигается на 2 узла вперед)• Список:
1 -> [2 (S)] -> 3 -> [4 (F)] -> 5 -
Шаг 2:
•
S: 3(двигается на 1 узел вперед)•
F: 5(двигается на 2 узла вперед)• Список:
1 -> 2 -> [3 (S)] -> 4 -> [5 (F)] -
Конец:
• Быстрый указатель (F) достигает конца списка или выходит за его пределы.
• Медленный указатель (S) находится на 3, который и является средним элементом.
Итоговый результат: Средний элемент списка 3.
Комментарии (49)
IvanZaycev0717
04.08.2024 10:48Хочу поинтеросоваться у автора - каким образом была выбрана задача? Когда я проходил собеседование, мне сказали написать random.randrange (3000) и что выведится в консоль, то и решай.
idsulik Автор
04.08.2024 10:48В первую очередь подбираю задачи, так чтобы объяснить какую-то тему, которая будет полезна на интервью, на примере этой задачи или саму задачу, которая часто встречается на интервью.
У меня на канале идут подряд задачи связанные с какой-то темой(two pointers, sliding window), сейчас перешел на тему fast and slow pointer и на примере этой задачи объяснил, что это такое + объяснил что такое связный список и какие они бывают(на видео).
Мне вот давали Reverse Linked List(фаанг в РФ) и десятки других задач(easy/medium/hard).
NevoWin
04.08.2024 10:48+43 вариант не лучше, чем второй. В 3 варианте за один проход, но в этом 1 проходе нужно двигать 2 указателя, с точки зрения количества операций будет одинаково со 2 вариантом.
Единственное, что в 3 варианте более красивая и элегантная идея.
Но 2 вариант проще в понимании и чтении кода в будущем.
Я бы взял на работу того, кто не усложняет код, где это не требуется, а пишет более просто.
wataru
04.08.2024 10:48Второй и третий варинаты имеют одинаковое количество сравнений и обращений к памяти.
Но из-за архитектурных ньюансов, сложно сказать, какой будет быстрее.
Третий вариант имеет меньше условных переходов (n/2 в случае одного цикла и n+n/2 в случае двух). Но это хорошо предсказываемые условные переходы на следующую итерацию цикла, поэтому они относительно дешевые.
С другой стороны, во втором варианте циклы короче.
С точки зрения кода второй вариант лучше, я с вами согласен.
idsulik Автор
04.08.2024 10:48Согласен, что третий вариант довольно хитрий и да, второй вариант проще в понимании
SquareRootOfZero
04.08.2024 10:48Идея 3 варианта довольно проста, только "у кого-то это щёлкает, а у кого-то не щёлкает". Предварить реализацию коротеньким комментарием о том, что происходит и почему это работает, и по лёгкости понимания и чтения оно, на мой взгляд, не только не уступит второму варианту, а даже его превзойдёт.
x89377
04.08.2024 10:48Хорошо было бы добавить голосование, что бы каждый мог выбрать правильный вариант № 3.
idsulik Автор
04.08.2024 10:48Самый оптимальный вариант третий) а две другие лишь подводят к третьему
aamonster
04.08.2024 10:48Вы проверили? Асимптотика у второго и третьего одинаковая, стоило сделать бенчмарк.
В боевом коде не задумываясь писал бы второй ("пиши код так, будто поддерживать его будет склонный к насилию психопат, знающий, где ты живёшь").
kibergus
04.08.2024 10:48Быстрый и медленный указатель имеет ровно такую же сложность, как и с подсчетом длины. Оба требует два прохода.
idsulik Автор
04.08.2024 10:48согласен, в случае с быстрым и медленным указателем, проходим каждый элемент 1.5 раз, но в рамках одного цикла
aamonster
04.08.2024 10:48Быстрый и медленный указатель, вероятно, тиснуты из более сложной задачки про кольцевой список :-)
idsulik Автор
04.08.2024 10:48не понял про кольцевой список
aamonster
04.08.2024 10:48Google "поиск цикла в односвязном списке" или "алгоритм черепахи и зайца".
Вкратце: у нас есть односвязный список неизвестной длины, возможно, он с какого-то места зацикливается. Надо узнать, зацикливается ли, и определить длину цикла и точку входа в него.
SquareRootOfZero
04.08.2024 10:48По Big-O такую же, одинаковое количество переходов к следующему элементу, но в третьем варианте отсутствуют операции сравнения текущего индекса указателя с вычисленной длиной списка, делённой пополам. Впрочем, выше @wataru, по-моему, уже написал про то же самое.
kibergus
04.08.2024 10:48+2Если хочется извращений, можно съэкономить половину итераций на втором итераторе: заводим два допонительных итератора i1, i2. Когда основной прохтдит через степень двойки (2, 4, 8, 16,...) сохраняем:
i1 = i2
i2 = i
Теперь когда дойдем до конца списка у нас есть закешированный итератор, который между 1/4 и 1/2 длины.
Но общая сложность все равно линия.
SpiderEkb
Если мне приходится делать реализации списков, я обычно сразу закладываю туда счетчик элементов. Если реализован двусвязный список, то любой элемент по номеру можно получить не более чем за length / 2 шагов - если n <= length / 2 - считаем с начала списка, иначе - с конца.
Вообще, двусвязный список предпочитаю делать кольцевым с двумя типами узлов.
Один узел имеет тип HEAD и содержит счетчик элементов и ссылки на первый и последний элементы списка (при необходимости там же могут быть какие-то другие свойства списка). Остальные элементы имеют тип NODE и содержат блок данных и ссылки на следующий и предыдущий элементы (первый в качестве предыдущего ссылается на HEAD, последний, в качестве следующего, аналогично ссылается на HEAD.
Сам объект "список" - это ссылка на HEAD.
idsulik Автор
Это тоже хороший и полезный способ, но все зависит от самой задачи, если достаточно односвязного списка без доп. данных, то нет смысла добавлять доп. данные, а если для задачи полезно держать какие-то данные в узлах, то делаем так)
SpiderEkb
Да, конечно от задачи. Иногда вообще ничего не нужно - можно использовать готовые библиотечные реализации.
monpa
Тут структура данных неподходящая выбрана) Искать середину полной итерацией - ну такое себе развлечение.
YMA
Вариант с 2 указателями хорош для олимпиады - оптимально, изящно. Он приходит в голову сразу, когда читаешь заголовок.
А вот в реальной работе предпочитаю первый, с конвертацией списка в массив... Потому как обычно нахождением среднего элемента обработка данных не ограничивается, памяти сейчас много, а ждать пользователь не любит. ;)
idsulik Автор
А что если элементов действительно много? миллионы элементов, каждый элемент содержит большое количество данных?)
лучше за один проход решить, если такая возможность есть) и быстро и памяти потребляет мало
acsent1
Если нужно найти серединный элемент в таком случае, то значит где-то неверно выбрали способ хранения данных
idsulik Автор
ну да, если задача заключается в просто нахождении середины, то это неоптимальный вариант хранения данных
avost
Самое интересное в этом комментарии не озвучено :). Расскажите, пожалуйста, что это были за задачи (во множестве числе!), для решения которых вам приходилось не только использовать связные списки, но и писать свои реализации?
Я спрашиваю без подколок - иногда на тех же собеседованиях спрашивают когда linked list лучше, чем array list - обычно ничего вменяемого придумать не удаётся.
В практических, конечно, задачах, не в литкодных/олимпиадных.
idsulik Автор
надо было мне это объяснить на видео.
проблема массивов в том, что когда место заканчивается, тебе надо создать новый массив большего размера, скопировать туда все элементы старого массива и добавить новый элемент уже в новый массив, когда как linked list может расширяться сколько угодно и по одному элементу.
а вот реально применять связный список мне пока не приходилось)
SpiderEkb
Свои реализации делаются или когда что-то очень специфическое по данным, или когда готовой нет в наличии (такое тоже бывает в жизни), или когда нужна предельная эффективность вкупе с какой-то спецификой задачи и приспособить готовое получается достаточно коряво.
Список или массив... Нам часто приходится иметь дело с очень большими объемами данных. Память в целом не проблема, можно считать что она не ограничена. Но есть ограничение - 16Мб одним куском (ну можно 2Тб, но там уже приходится "танцевать вприсядку" - это другая модель памяти и, в общем случае, даже другой размер указателя). И вот если нет уверенности что получится выделить массив (даже динамический массив все равно в памяти одним куском будет), то тогда используется список.
Там еще есть варианты - списки ключ-данные с необходимостью поиска по ключу. Можно организовать это массивом, отсортировать его и потом использовать быстрый двоичный поиск (быстрее не бывает). Но тут есть момент - если у нас данные постоянно меняются, то каждый раз пересортировывать массив из хотя бы сотни тысяч элементов (а для нас это не сказать чтобы сильно много) приводит просто к катастрофической потере производительности. И вот тут лучше список ключ-данные.
А если это статика - один раз заполнил, отсортировал и потом 100500 раз ищешь - там сортированный массив по производительности лучше.
Sap_ru
Нужен FIFO или LIFO доступ к элементам.
Нужны частые операции добавляения большого количества элементов или объединения списков.
Список состоит из элементов большого размера, может содержать большое колличество элеметнов и при этом все время растет. Использование массивов тут неоптимально по причине часто реаллокации больших объёмов памяти.
Массив состоит из структур и по причине экономии ресурсов или необходимости обеспечения эффекивного многопоточного атомарного доступа нужно, чтобы элементы структур были сразу элементами списка (т.е. отказ от работы с указателями даёт какие-то преимущества). Крайне редкая ситуация.
idsulik Автор
Лучше не опишешь, добавлю это в комментарии к видео и оставлю ссылку на источник)
aamonster
В практических задачах обычно linked list делается не отдельно, а поверх уже существующей структуры данных, чтобы выстроить в цепочку объекты, которые существуют без него. Как контейнер – не припомню...
idsulik Автор
не понял этот момент, что имеется в виду?
aamonster
В смысле у вас уже есть какое-то хранилище объектов (массив, дерево, ещё что – что вам диктует задача) и вам понадобилось для каких-то нужд объединить эти объекты в цепочки. Можно хранить отдельно списки указателей на ваши объекты, а можно просто добавить в каждый объект поле next.
idsulik Автор
ну это как-то не очень, лучше создать LinkedList, чтобы код был чище)
aamonster
Ага, и фигакнуть на ровном месте по выделению памяти в куче на каждый элемент.
idsulik Автор
ну значение ноды будет ССЫЛКА на нужный объект, поэтому не вижу в этом проблем) ну или плохо понял идею
aamonster
Ага, только на N объектов вам придётся выделить N нод. Каждая будет хранить указатель на объект, указатель на следующую ноду + накладные расходы кучи. И затраты времени на выделение/освобождение.
А если вы прямо внутри вашего объекта сделаете поле указателя на следующий – это куда выгоднее.
Если же вам надо очередь делать снаружи, не модифицируя объекты – обычно выгоднее (и по памяти, и по быстродействию) кольцевой буфер.
idsulik Автор
На самом деле есть место и тому и другому и третьему варианту) тут зависит от конкретной задачи.
Но я не знаю кейса, где понадобится такая оптимизация, что нужно менять объякты и добавлять туда указатели, вместо использования linked list
aamonster
Я за 29 лет практики не припомню задачи, где мне понадобился бы именно отдельный Linked list :-)
idsulik Автор
тоже не припоминаю) ни в том, ни в другмо виде
wataru
Например, при реализации LRU кеша. Там при доступе у ключу, он перемещается в конец списка. При переполнении кеша (хеш таблица значений), удаляется элемент из начала списка.
SpiderEkb
Например, в ситуациях, когда по какой-причине нужно вставлять или удалять элементы внутри цепочки.
aamonster
Учитывая, что чтобы вставить или удалить элемент, нужно вначале найти его место за O(n) – редко когда linked list в качестве контейнера оправдан.
SpiderEkb
Простейший случай - идете по цепочке от начала к концу и для каждого элемента принимаете решение - оставить его или удалить. Такой вот play-off алгоритм.
Есть еще очереди. Например, на отправку сообщений. Сообщение для отправки берется из начала очереди. Новые сообщения добавляются в конец. Отправленное (точнее, отправленное на которое получено подтверждение о поиеме) сообщение удаляется из начала очереди.
aamonster
Очередь обычно делается кольцевым буфером, не linked list. Исключение – когда объекты уже лежат где-то и вы их просто связываете прямо на месте.
Play-off – тот же один проход по массиву (двумя указателями) удаляет всё лишнее за O(n), как и в случае linked list.
Я не говорю, что linked list нигде не пригодится, но его использование в качестве контейнера – лютая экзотика.
wataru
Ничего не мешает держать хеш-таблицу из идентификаторов элементов в указатели/итераторы в list. Популярное применение - LRU cache. Там список навешан сверху на хеш-таблицу и задает порядок элементов, чтобы выбирать, какой элемент самый старый и его надо удалить. При доступе элемент из центра списка будет перемещен в конец.
aamonster
Это то, про что я говорил: linked list не как контейнер, а связываем хранящиеся отдельно данные.