Алгоритми та структури даних · Middle · Запитання 24 з 75
Як знайти цикл у зв'язному списку з O(1) додаткової пам'яті?
- ✓Правильна відповідь: Повільний і швидкий вказівники: вони зустрінуться лише за наявності циклу
- 2Порахувати вузли й порівняти з властивістю довжини списку
- 3Зберігати кожен відвіданий вузол у
Setі шукати повтори
Пояснення
Це алгоритм Флойда «черепаха й заєць». Якщо цикл є, швидкий вказівник рано чи пізно наздожене повільного; якщо немає, дійде до null. Set теж працює, але займає O(n) пам'яті.