Алгоритми та структури даних · Middle · Запитання 25 з 75
Як знайти середину зв'язного списку за один прохід?
- ✓Правильна відповідь: Повільний і швидкий вказівники: коли швидкий дійде до кінця, повільний буде посередині
- 2Прочитати властивість довжини списку й перейти до
length / 2 - 3Розвернути список і йти з обох кінців, доки вони не зустрінуться
Пояснення
Однозв'язний список не знає своєї довжини, тож інакше знадобилося б два проходи. Прийом із повільним і швидким вказівниками знаходить середину за один прохід з O(1) пам'яті.