0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>20 фев 2023</li>
2
<ul><li>20 фев 2023</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: понять, зациклен ли связный список</h2>
4
</ul><h2>Задача: понять, зациклен ли связный список</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся узнать, есть ли в списке цикл.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся узнать, есть ли в списке цикл.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Дана голова связного списка - head. Определить, зациклен ли этот список. Вернуть true, если зациклен, иначе - false.</p>
8
<p><strong>Условие.</strong>Дана голова связного списка - head. Определить, зациклен ли этот список. Вернуть true, если зациклен, иначе - false.</p>
9
<p><strong>Пояснение.</strong>Связный список - это список из объектов, которые связаны друг с другом. Каждый элемент состоит из двух компонентов: собственно данных и ссылки на следующий элемент. Головой связного списка называют его первый элемент. Конечный элемент - это хвост. Главное отличие хвоста от остальных элементов в том, что его ссылка на следующий элемент - это null.</p>
9
<p><strong>Пояснение.</strong>Связный список - это список из объектов, которые связаны друг с другом. Каждый элемент состоит из двух компонентов: собственно данных и ссылки на следующий элемент. Головой связного списка называют его первый элемент. Конечный элемент - это хвост. Главное отличие хвоста от остальных элементов в том, что его ссылка на следующий элемент - это null.</p>
10
<p>Список будет зациклен, если его хвостовой элемент указывает не на null, а на индекс другого элемента. В таком случае мы будем бесконечно перебирать элементы списка и никогда не достигнем его конца. Изначально мы не видим, есть ли в списке цикл, но на это будет указывать индекс pos. Если он равен положительному значению, значит, хвостовой элемент соединён с другим, а если он отрицательный - значит, цикла нет.</p>
10
<p>Список будет зациклен, если его хвостовой элемент указывает не на null, а на индекс другого элемента. В таком случае мы будем бесконечно перебирать элементы списка и никогда не достигнем его конца. Изначально мы не видим, есть ли в списке цикл, но на это будет указывать индекс pos. Если он равен положительному значению, значит, хвостовой элемент соединён с другим, а если он отрицательный - значит, цикла нет.</p>
11
Ввод: head = [3,2,0,-4], pos = 1 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 1. Ввод: head = [1,2], pos = 0 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 0. Ввод: head = [1], pos = -1 Вывод: false Пояснение: цикл создать нельзя.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
11
Ввод: head = [3,2,0,-4], pos = 1 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 1. Ввод: head = [1,2], pos = 0 Вывод: true Пояснение: цикл можно образовать, если соединить последний узел с узлом под индексом 0. Ввод: head = [1], pos = -1 Вывод: false Пояснение: цикл создать нельзя.<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
12
<p><strong>Решение</strong></p>
12
<p><strong>Решение</strong></p>
13
<p>Мы будем использовать следующий принцип двух бегунков в цикле: если один из них будет быстрее, то он обязательно догонит медленный.</p>
13
<p>Мы будем использовать следующий принцип двух бегунков в цикле: если один из них будет быстрее, то он обязательно догонит медленный.</p>
14
<p>Поэтому мы возьмём два бегунка - быстрый и медленный, а затем проитерируем по всему списку до конца. Конец в нашем случае - это один из двух вариантов: первый - список имеет цикл и бегунки встретятся, второй - мы будем иметь null в конце списка.</p>
14
<p>Поэтому мы возьмём два бегунка - быстрый и медленный, а затем проитерируем по всему списку до конца. Конец в нашем случае - это один из двух вариантов: первый - список имеет цикл и бегунки встретятся, второй - мы будем иметь null в конце списка.</p>
15
<p>Давайте реализуем это в коде:</p>
15
<p>Давайте реализуем это в коде:</p>
16
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; }<p><strong>Результаты</strong></p>
16
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; }<p><strong>Результаты</strong></p>
17
<p><strong>Временная сложность:</strong>O(n) - так как мы однократно проходимся по всему массиву.</p>
17
<p><strong>Временная сложность:</strong>O(n) - так как мы однократно проходимся по всему массиву.</p>
18
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
18
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти.</p>
19
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>
19
<a>Научитесь: Профессия Java-разработчик + ИИ Узнать больше</a>