Решение задачи с собеседования Linked List Cycle [+ ВИДЕО] / forpes.ru

Главная
Решение задачи с собеседования Linked List Cycle [+ ВИДЕО]

Решение задачи с собеседования Linked List Cycle [+ ВИДЕО] +1

28.10.2024 08:19

idsulik 27 1100 Источник

На видео более подробное объяснение каждого решения

Постановка задачи

Ссылка на задачу: https://leetcode.com/problems/linked-list-cycle

Дан head, являющийся головой связного списка, необходимо определить, есть ли в списке цикл.
Цикл в связном списке существует, если есть такой узел, до которого можно снова добраться, непрерывно следуя указателям next. Внутренне используется переменная pos, чтобы указать индекс узла, к которому присоединен указатель next последнего узла (хвоста). Обратите внимание, что pos не передается как параметр.
Верните true, если в связном списке есть цикл. В противном случае верните false.

1. Решение с использованием set

Подход

Для решения задачи о проверке наличия цикла в связном списке можно использовать структуру данных set. Мы будем проходить по всем узлам списка и сохранять каждый посещенный узел в set. Если мы встречаем узел, который уже есть в этом множестве, значит, в списке есть цикл. Если мы дошли до конца списка, не встретив повторяющегося узла, значит, цикла нет.

Алгоритм

Инициализируем пустое множество seen, чтобы хранить посещенные узлы.
Начинаем с головы списка head.
Пока текущий узел не равен None:

• Если текущий узел уже есть в seen, возвращаем true — в списке есть цикл.

• Если текущего узла нет в seen, добавляем его в множество.

• Переходим к следующему узлу.
Если дошли до конца списка (указатель next на последнем узле равен None), возвращаем false — цикла нет.

Код решения

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()

        while head:
            if head in seen:
                return True
            
            seen.add(head)
            head = head.next
        
        return False

Сложность алгоритма

По времени: O(n), где n — количество элементов в списке, так как мы проходим по каждому элементу один раз.
По памяти: O(n), так как мы сохраняем все уникальные элементы списка в множество.

Визуализация

Пример 1 (Список без цикла)

Исходный список:

1 -> 2 -> 3 -> 4 -> 5 -> None

Текущий узел: 1, seen = {1}
Текущий узел: 2, seen = {1, 2}
Текущий узел: 3, seen = {1, 2, 3}
Текущий узел: 4, seen = {1, 2, 3, 4}
Текущий узел: 5, seen = {1, 2, 3, 4, 5}

Результат: False, так как узлы не повторяются и конец списка был достигнут.

Пример 2 (Список с циклом)

Исходный список:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |---------|

Текущий узел: 1, seen = {1}
Текущий узел: 2, seen = {1, 2}
Текущий узел: 3, seen = {1, 2, 3}
Текущий узел: 4, seen = {1, 2, 3, 4}
Текущий узел: 5, seen = {1, 2, 3, 4, 5}
Текущий узел: 3 (уже в seen)

Результат: True, так как узел 3 повторяется, следовательно, есть цикл.

2. Решение с использованием двух указателей

Подход

В этом решении используется техника двух указателей — медленного (slow) и быстрого (fast). Они оба начинаются с головы списка, но slow двигается на один узел за раз, а fast — на два узла. Если в списке есть цикл, то в какой-то момент slow и fast встретятся в одном узле. Если fast достигнет конца списка (т.е. fast или fast.next станет None), значит, цикла нет.

Алгоритм

Инициализируем два указателя: slow и fast, оба начинаются с головы списка head.
Запускаем цикл, пока fast и fast.next не равны None:

• Двигаем slow на один шаг вперед.

• Двигаем fast на два шага вперед.

• Если slow и fast встретились, возвращаем True — в списке есть цикл.
Если цикл завершился без встречи указателей, возвращаем False — цикла нет.

Код решения

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True
        
        return False

Сложность алгоритма

По времени: O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
По памяти: O(1), так как мы используем только два указателя для обхода списка и не занимаем дополнительную память.

Визуализация

Пример 1 (Список без цикла)

Исходный список:

1 -> 2 -> 3 -> 4 -> 5 -> None

Инициализация:

1 -> 2 -> 3 -> 4 -> 5 -> None
slow
fast

Шаг 1:

1 -> 2 -> 3 -> 4 -> 5 -> None
     slow
          fast

Шаг 2:

1 -> 2 -> 3 -> 4 -> 5 -> None
          slow
                    fast

Шаг 3:

1 -> 2 -> 3 -> 4 -> 5 -> None
               slow
                            fast (достиг конца)

Результат: False, так как быстрый указатель достиг конца списка и указатели не встретились.

Пример 2 (Список с циклом)

Исходный список:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |---------|

Инициализация:

1 -> 2 -> 3 -> 4 -> 5
slow
fast

Шаг 1:

1 -> 2 -> 3 -> 4 -> 5
     slow
          fast

Шаг 2:

1 -> 2 -> 3 -> 4 -> 5
          slow
                    fast

Шаг 3:

1 -> 2 -> 3 -> 4 -> 5
               slow
          fast (по циклу вернулся на 3)

Шаг 4:

1 -> 2 -> 3 -> 4 -> 5
                    slow
                    fast (встретились на 5)

Результат: True, указатели встретились на узле со значением 5, что указывает на наличие цикла.

Комментарии (27)

wataru
28.10.2024 09:45
#27477978
O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.

Не правда. "Быстрый" указатель может по циклу сделать очень и очень много полных оборотов.

Ну и по статье - разбор баянистых элементарных задачек надо делать не так. Люди, которые их уже знают, от вашей статьи не получили ничего. Люди, которые их не умеют решать, от вашей статьи тоже не получили ничего, потому что им ничего не понятно. Максимум, что они тут могут сделать - это выучить код наизусть. Сомнительной полезности действие.

Вам надо не только приводить код решения (причем два раза: первый раз текстом, второй раз кодом), а объяснять, почему и как оно работает.
1. Zara6502
  28.10.2024 09:45
  #27478124
  скорее всего там никогда не будет O(n*n), а всегда будет O(k*n) где k*n < n*n, что в BigO() нотации эквивалентно O(n). У вас n элементов в списке и кольцо на первый элемент, это даёт 2*n в максимуме.
  1. wataru
    28.10.2024 09:45
    #27478188
    Там все еще будет O(n), потому что медленный указатель, действительно, пройдет по каждому элементу не более 1 раза (после того, как он ступит на цикл, быстрый догонит его раньше, чем он сделает полный круг). Быстрый делает 2 шага на 1 шаг медленного, поэтому общее количество ходов будет не больше 3n.
    
    Вот только это надо все расписать.
    
    idsulik Автор
    28.10.2024 09:45
    #27478316
    Вот только это надо все расписать.
    
    почему вы так считаете?)
    
    wataru
    28.10.2024 09:45
    #27478436
    Потому что иначе в статье нет никакой пользы. Вы же зачем-то попытались аргументировать, почему там O(n) будет? Правда, с ошибкой.
    
    idsulik Автор
    28.10.2024 09:45
    #27478940
    Потому что иначе в статье нет никакой пользы
    
    ну видимо нет пользы для вашего уровня, надеюсь найдутся люди, для которых статья будет полезной)
    
    wataru
    28.10.2024 09:45
    #27479078
    надеюсь найдутся люди, для которых статья будет полезной)
    
    Очень вряд ли. Вот так как вы объясняете - начинающим не понятно. Говорю как человек с опытом преподавания. Ваш текст вообще лишь дублирует код. Он должен объяснять не "что", а "как", "откуда" и "почему". Поскольку задача очень широко известная, то любой не совсем начинающий ее уже знает.
    
    Соответственно, вам надо или задачи посложнее и не такие известные брать, или разъяснять почему вот это работает в тексте.
    
    idsulik Автор
    28.10.2024 09:45
    #27479256
    Если есть примеры, где объясняется лучше, напишите, гляну
    
    wataru
    28.10.2024 09:45
    #27479326
    Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
    
    idsulik Автор
    28.10.2024 09:45
    #27479532
    Спасибо за пример, но мне больше нравится формат в котором я пишу, для новичков, а не с математическими доказательствами)
    
    wataru
    28.10.2024 09:45
    #27479594
    Ну совсем без математики нельзя. Все-таки алгоритмы - это computer science, которая является областью математики. Ну можно хотя бы словами объяснить почти все.
    
    Основная идея: когда медленный указатель зайдет на цикл, за одну итерацию расстояние между ними уменьшается на 1. В итоге за конечное число шагов (меньше длины цикла) быстрый указатель догонит медленного. Было между ними растояние L (если считать по циклу от быстрого), а стало L+1 - 2 = L-1 (+1 - медленный ушел вперед -2 - быстрый пошел вслед за ним). Поэтому, кастати, не надо проверять, не догнал ли быстрый указатель медленный дополнительно в середине его длинного шага - заяц через черепаху не перепрыгнет. Поэтому алгоритм рано или поздно остановится.
    
    Еще можно было бы объяснять прогрессивно, по уровням, как до этого можно додуматься. Начнем с задачи проверить, является ли список замкнутым циклом, или линией вообще без циклов. Можно проверять одним указателем совпадение с перым элементом. Но если первый элемент не на цикле, то это не работает. Надо взять какой-то элемент в цикле. Но неизвестна же длина начала, поэтому нельзя сначала сделать много шагов, ибо неясно, а сколько их будет достаточно. Значит надо этот помеченный элемент в цикле двигать вперед. Но тогда сам указатель надо двигать на 2 шага, чтобы продвижение вперед, все-таки было.
    
    И про время работы, если бы вы хотя бы примерно стали считать, а сколько там операций то происходит, то не ошиблись бы в рассуждениях.
    
    wataru
    28.10.2024 09:45
    #27479330
    Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
    
    Zara6502
    28.10.2024 09:45
    #27481320
    По времени: O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
    
    У вас ошибка, указатель, который быстрый, может пройти по некоторым элементам списка не один раз (видимо от 1 до 2*n раз, в среднем n/2).
    
    А O(n) там будет из-за константного характера числа итераций, то есть будет O(k*n) где k*n < n*n, хотя в комментариях и есть вырожденный случай с одним элементом списка, который даст 3*n, что формально можно назвать и O(n*n*n), но так как там единица, то это чисто виртуальный куб.
    
    wataru
    28.10.2024 09:45
    #27482260
    Вы, похоже, не очень понимаете, что такое O().
    
    3*n = O(n), а не O(n^3) *
    
    O(n) - означает, что время работы в худшем случае (т.е. количество операций) алгоритма растет не быстрее линейного. Обычно считают худший случай, если не сказано специально, что это средняя оценка. Т.е. увеличели вы n в 10 раз - количество операций увеличилось не больше чем в 10 раз.
    
    3*(n*10) = 10*(3*n) - количество операций увеличилось ровно в 10 раз. Тут O(n).
    
    Для этого надо как-то оценить количество операций сверху. Иногда можно просто посчитать в лоб, иногда надо как-то что-то округлять. В этой задаче ограничение выводится просто: медленный указатель сделает не больше n шагов, быстрый сделает в 2 раза больше. Итого получается не больше 3n шагов. По идее надо еще считать все сравнения: цикл сделает по одному сравнению на каждую итерацию, которых не более n. Суммарно количество операций не более 4n. Обратите внимание, тут не считают какая операция медленная, а какая быстрая, может сравнение на самом деле это несколько операций: вычитание регистров и условный переход. Потому что в конце мы используем O(), которое константы отбрасывает и можно считать что все операции одинаково медленные.
    
    будет O(k*n)
    
    Что за k вообще? Если k - это константа, то она отбрасывается в O(). И остается O(n). В скобках должны остаться только параметры входных данных. Тут в задаче есть только n, поэтому в никаких других букв в оценку вставлять вообще не должны. У вас может быть O(n), O(n^10), O(2^n), O(log n), но никаких k там быть не должно.
    
    даст 3*n, что формально можно назвать и O(n*n*n), но так как там единица, то это чисто виртуальный куб.
    
    Как вы из 3n получили n^3 вообще непонятно. Что за единица, что за виртуальный куб?
    
    *примечание
    Формально n = O(n^3) и n = O(n^1000) - ибо эта запись означает оценку сверху, ограничение. Тут знак равенства вообще не является равенством в привычном смысле - это просто перегрузка нотации. Но принято использовать минимальную оценку, иначе смысла что-то оценивать вообще нет. Поэтому оценивать 3n как n*n*n - не правильно.
    
    Zara6502
    28.10.2024 09:45
    #27482508
    
    Вы, похоже, не очень понимаете, что такое O().
    
    3*n = O(n), а не O(n^3) *
    
    Я прекрасно понимаю что такое O().
    
    Что за k вообще? Если k - это константа, то она отбрасывается в O()
    
    Отбрасывайте, я не запрещаю, я лишь показываю что там нет n^2
    
    Как вы из 3n получили n^3 вообще непонятно. Что за единица, что за виртуальный куб?
    
    Поэтому оценивать 3n как n*n*n - не правильно.
    
    Я знаю что O(1) и O(n) при n=1 это совсем не то же самое и сравнивать эти вещи не пытаюсь, но алгебраически 3*1 = 1^3 и вроде ничто не мешает использовать этот факт.
    
    wataru
    28.10.2024 09:45
    #27482606
    Отбрасывайте, я не запрещаю, я лишь показываю что там нет n^2
    
    Так что за k? и как у вас там нет n^2, если ниже вы утверждаете, что там n^3? Хоть и "виртуальное"?
    
    , но алгебраически 3*1 = 1^3
    
    Что? 3*1 = 3. 1^3 = 1. 3!= 1
    
    Zara6502
    28.10.2024 09:45
    #27482962
    Так что за k? и как у вас там нет n^2, если ниже вы утверждаете, что там n^3? Хоть и "виртуальное"?
    
    k - коэффициент, он не учитывается
    
    Что? 3*1 = 3. 1^3 = 1. 3!= 1
    
    Ох я и красавец. (ищет пепел)
    
    Zara6502
    28.10.2024 09:45
    #27478562
    Вы написали "Не правда", не ясно к какой части цитаты это относится, к O(n) или к утверждению что указатели "пройдут по каждому элементу 1 раз".
    
    Про O(n) я ответил, про "1 раз" я не комментировал. Но легко увидеть, что если кольцо сделать на элемент n/2+1 то указатели не встретятся и быстрый пробежит кольцо второй раз (что делает утверждение автора ошибочным), что даст k=2*n в любом случае.
    
    А для какого цикла вы прогнозируете 3*n?
    
    wataru
    28.10.2024 09:45
    #27478620
    не ясно к какой части цитаты это относится
    
    к " "пройдут по каждому элементу 1 раз". Извиняюсь за неточность.
    
    А для какого цикла вы прогнозируете 3*n?
    
    Для любого. Это оценка сверху. Худший случай будет, если цикл длины 1. Тогда медленный пройдет все вершины по 1 разу, а быстрый пройдет все вершины + последнюю еще n (или n-1) раз.
    
    Zara6502
    28.10.2024 09:45
    #27478854
    Для любого. Это оценка сверху. Худший случай будет, если цикл длины 1. Тогда медленный пройдет все вершины по 1 разу, а быстрый пройдет все вершины + последнюю еще n (или n-1) раз.
    
    вырожденный случай, понял
1. idsulik Автор
  28.10.2024 09:45
  #27478306
  разбор баянистых элементарных задачек надо делать не так
  
  а можно ваши регалии, чтобы понять кто указывает как надо, а как не надо?)
  1. wataru
    28.10.2024 09:45
    #27478422
    Переход на личности - лучший аргумент, да. /s
    
    Могу предложить: медали с чемпионатов мира по программированию, PhD по computer science, преподавание в лагерях по подготовке школьников к олимпиадам по программированию, много лет проведения интервью в гугле, 1300 решенных задачек на литкоде. Еще что-то нужно, прежде чем вы даруете мне право критиковать статьи про задачки в интернете?
    
    Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
    
    idsulik Автор
    28.10.2024 09:45
    #27478964
    Буквально восприняли вопрос, не переходил на личности и не собирался, если так вышло - извиняюсь.
    Вопрос был больше про - с чего вы решили, что вы лучше знаете как надо делать, а как не надо? И если вы знаете как надо, то делайте, приносите пользу)
    
    Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
    
    не стоит)

Alexandroppolus
28.10.2024 09:45
#27478182
О быстром и медленном указателях для этой задачи несколько раз писали на Хабре. Так же известно, что если стартовать два медленных указателя, один от начала списка, другой от места встречи fast и slow, то новая встреча будет как раз в узле, на который ссылается хвост. Доказательство этого факта внесло бы новизну в тему.
1. idsulik Автор
  28.10.2024 09:45
  #27478328
  Насчет предложения - это будет в рамках другой задачи, где как раз нужно найти такой узел https://leetcode.com/problems/linked-list-cycle-ii/description/

webhamster
28.10.2024 09:45
#27479128
указатели встретились на узле со значением 3, что указывает на наличие цикла.

Но ведь они встретились на узле 5. Вы же сами нарисовали это пошагово.
1. idsulik Автор
  28.10.2024 09:45
  #27479260
  спасибо, исправил

Решение задачи с собеседования Linked List Cycle [+ ВИДЕО] +1

Постановка задачи

1. Решение с использованием set

Подход

Алгоритм

Код решения

Сложность алгоритма

Визуализация

2. Решение с использованием двух указателей

Подход

Алгоритм

Код решения

Сложность алгоритма

Визуализация

Комментарии (27)

idsulik Автор

idsulik Автор

idsulik Автор

idsulik Автор

idsulik Автор

idsulik Автор

idsulik Автор

idsulik Автор