Обнаружение цикла в связном списке
Дан односвязный список head. Верните true, если в списке есть цикл, и false в противном случае.
Цикл в связном списке существует, если хотя бы один узел может быть посещен повторно, следуя по указателю next.
Ограничения:
- Длина списка:
1 <= длина <= 1000. - Значение узла:
-1000 <= Node.val <= 1000. - Параметр
index(не передается в функцию) определяет индекс начала цикла, если он существует. Еслиindex = -1, цикл отсутствует.
Пример 1:
Input: head = [1, 2, 3, 4], index = 1 Output: true
Пример 2:
Input: head = [1], index = -1 Output: false
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью
O(1) для оптимального подхода.
Подсказка 1
Решение грубой силы заключалось бы в использовании хеш-таблицы для хранения посещенных узлов. Это было бы решение
с временной сложностью O(n) и пространственной сложностью O(n). Можете ли вы придумать
более эффективный способ?
Подсказка 2
Можно ли использовать два указателя, движущихся с разной скоростью, чтобы обнаружить цикл?
Подсказка 3
Используйте метод "черепахи и зайца" (алгоритм Флойда), чтобы обнаружить цикл без использования дополнительной памяти.