Список brainteasers
Домой
Территория Web 1.0 / Brainteasers
Цикл в списке
Ответ (линейная сложность)
Пускаем по списку два указателя с разной скоростью.
То есть, на первом шаге и в первую (обозначим ее через A), и во вторую (B) ячейки памяти кладем первый элемент. Далее каждый шаг сдвигаем первую ячейку дальше по списку, а вторую сдвигаем только каждый второй шаг.
То есть:
* Шаг1: A -> 1, B -> 1
* Шаг2: A -> 2, B -> 1
* Шаг3: A -> 3, B -> 2
* Шаг4: A -> 4, B -> 2
* Шаг5: A -> 5, B -> 3
...
Если они встретятся ("медленная" ячейка догонит "быструю"), значит в списке есть цикл.
Условие
Подсказка [1]
Подсказка [2]
Ответ [1]
16.03.2010