Изменения

Перейти к: навигация, поиск

Список

1 байт добавлено, 18:27, 11 июня 2014
Задача на поиск цикла в списке
'''return''' ''true''
Возможны два варианта цикла в списке. Первый вариант - сам список циклический(указатель next последнего элемента равен первому), а второй вариант - цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся , будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting)
Анонимный участник

Навигация