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

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

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

Дмитрий Зверев

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

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

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

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

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

Ввод и вывод. Пример 1

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

Пример 2

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

Пример 3

Ввод: 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;
    }