Задача: понять, зациклен ли связный список
2026-02-21 17:47 Diff
https://skillbox.ru/media/code/zadacha-ponyat-zatsiklen-li-svyaznyy-spisok/

#статьи

  • 20 фев 2023
  • 0

Задача: понять, зациклен ли связный список

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся узнать, есть ли в списке цикл.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Дана голова связного списка — head. Определить, зациклен ли этот список. Вернуть true, если зациклен, иначе — false.

Пояснение. Связный список — это список из объектов, которые связаны друг с другом. Каждый элемент состоит из двух компонентов: собственно данных и ссылки на следующий элемент. Головой связного списка называют его первый элемент. Конечный элемент — это хвост. Главное отличие хвоста от остальных элементов в том, что его ссылка на следующий элемент — это null.

Список будет зациклен, если его хвостовой элемент указывает не на null, а на индекс другого элемента. В таком случае мы будем бесконечно перебирать элементы списка и никогда не достигнем его конца. Изначально мы не видим, есть ли в списке цикл, но на это будет указывать индекс pos. Если он равен положительному значению, значит, хвостовой элемент соединён с другим, а если он отрицательный — значит, цикла нет.

Ввод: head = [3,2,0,-4], pos = 1 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 1. Ввод: head = [1,2], pos = 0 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 0. Ввод: head = [1], pos = -1 Вывод: false Пояснение: цикл создать нельзя.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Мы будем использовать следующий принцип двух бегунков в цикле: если один из них будет быстрее, то он обязательно догонит медленный.

Поэтому мы возьмём два бегунка — быстрый и медленный, а затем проитерируем по всему списку до конца. Конец в нашем случае — это один из двух вариантов: первый — список имеет цикл и бегунки встретятся, второй — мы будем иметь null в конце списка.

Давайте реализуем это в коде:

public boolean hasCycle(ListNode head) { if(head == null || head.next == null){ return false; } ListNode fast = head.next; while(head != fast){ if (fast.next == null || fast.next.next == null){ return false; } else { head = head.next; fast = fast.next.next; } } return true; }

Результаты

Временная сложность: O(n) — так как мы однократно проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Научитесь: Профессия Java-разработчик + ИИ Узнать больше