Список 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