Mediumlinked-listfloyd
Как определить цикл в связном списке?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 141. Алгоритм Floyd's Tortoise and Hare: два указателя, slow (1 шаг) и fast (2 шага). Если есть цикл — fast догонит slow. O(n) время, O(1) память.
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseНайти начало цикла (LeetCode 142): после встречи запускаем ещё один указатель от head; оба идут по 1 шагу и встретятся в начале цикла. Альтернатива — HashSet seen nodes (O(n) время и память). Тот же приём slow/fast — для нахождения middle списка и проверки palindrome.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.