Еще одна задача в продолжение задачи об односвязных списках.
Дано: односвязный список N1->N2->N3->... и указатель на его голову N1. Существует вероятность, что список зациклен, и узел Nn указывает на любой из узлов списка. Например, так N1->N2->N3->N4->...->Nn->N3->N4->... .
Нужно: разработать алгоритм, определяющий наличие цикла в списке (да/нет).
Может что то вроде
ОтветитьУдалитьclass Guard
{
Guard(WrapperValueType const &el)
{
if (el.locked())
{
throw std::exception("ПЫЩ!!!111ПЫЩ!!!111");
}
el.lock();
}
~Guard()
{
el.unlock();
}
}
, где WrapperValueType это элемент списка и bool с делегированными операциями.
И рукурсивно пройти список до конца =)
Так как никаких условий на то, что список должен остаться неизменным, не наложено, то я бы сначала предложил пройтись от головы, сбрасывая указатель next у каждого обработанного элемента (сброс - установка значения, явно указывающего на отсутствие следующего элемента, и отличное от значения, указывающего на конец списка), а при обработке следующего элемента, проверять "сброшено" ли значение next, если сброшено, то список зациклен. Держим в голове потенциальные проблемы с памятью и тем, что список будет изменен после такой проверки, но ведь на этот счет ничего не говорилось:)
ОтветитьУдалитьЕсли первый вариант не будет встречен овациями, то можно придумать что-нибудь с внесением избыточности в данные (дополнительные структуры, вроде того, что предложил Андрей, или что-то менее красивое со списками адресов\идентификаторов), чтобы иметь возможность для очередного узла однозначно определить то, что он уже обрабатывался, но все подобные решения чреваты тем, что мы ничего не знаем о списке и можем получить существенные трудности, связанные с разрастанием таких структур, поэтому подобные решения применимы в каких-то частных случаях, а не в общем.
Оптимальный и красивый алгоритм, связанный с запуском двух итераторов (один с единичным шагом, второй с шагом два), начали выуживать из своего сознания мои коллеги, но коллективный разум нас двигает медленно, а гуглить еще рано. Кто-нибудь помнит этот алгоритм?
Кстати, расширяя тему, интересно узнать, много ли тех, кто назубок понит помнит решения подобных задач (вроде бы простых, но заковыристых)? или же вы, немного пораскинув мозгами, выдаете близкий к оптимальному ответ? или, как, например, я, каждый раз проходите от "слабых" ответов к более эффективным?
Пожалуй, алгоритм с двумя итераторами -- самый оптимальный и самый простой для этой задачи. Хотя другие решения тоже вполне рабочие, ведь дополнительных ограничений действительно не озвучено.
ОтветитьУдалитьА ссылку на него можно?
ОтветитьУдалитьЧестно говоря, ссылки у меня нет. Если у кого есть -- дайте, плз.
ОтветитьУдалитьАлгоритм довольно простой: запускаем по списку два итератора с разной скоростью. Быстрый итератор либо дойдет до конца -- значит цикла нет, либо догонит медленный итератор -- значит цикл есть.
Забавн, спасибо.
ОтветитьУдалитьНесколько лет назад ентот вопрос мне задали тож на собеседовании:
ОтветитьУдалитьThis solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".
http://ostermiller.org/find_loop_singly_linked_list.html
О, большое спасибо за ссылку!
ОтветитьУдалить