Алгоритм циклического связанного списка

Question

Недавно меня попросили на собеседовании для разработки алгоритма, который может определить, является ли связанный список циклическим. Поскольку это связанный список, мы не знаем его размера. Это двусвязный список, где каждый узел имеет указатели «следующий» и «предыдущий». Узел может быть связан с любым другим узлом или он может быть связан с самим собой.

Единственное решение, которое я нашел в то время, - это выбрать узел и проверить его со всеми узлами в связанном списке. Интервьюеру явно не понравилась идея, так как это не оптимальное решение. Что было бы лучше?

Answer 1

Вы можете обрабатывать общий полный круговой список, например, так: перебирайте связанный список через первый элемент, пока не достигнете конца списка или пока не вернетесь к первому элементу.

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