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

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

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

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

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

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

Подход

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

Алгоритм

1. Инициализируем пустое множество seen, чтобы хранить посещенные узлы.

2. Начинаем с головы списка head.

3. Пока текущий узел не равен None:

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

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

   • Переходим к следующему узлу.

4. Если дошли до конца списка (указатель 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), значит, цикла нет.

Алгоритм

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

2. Запускаем цикл, пока fast и fast.next не равны None:

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

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

   • Если slow и fast встретились, возвращаем True — в списке есть цикл.

3. Если цикл завершился без встречи указателей, возвращаем 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, что указывает на наличие цикла.