Найти цикл в односвязном списке

Опубликовано Sep 22, 2011 в Связанные списки | 6 коммент.


Необходимо написать функцию, которая бы проверила односвязный список, заданный указателем на первый элемент, на наличие зацикливания.

 bool CheckLinkedList(LinkedListNode *firstItem)
{
  //ваш код
}
1 Цель задания проверка навыков алгоритмического мышления
2 Время выполнения 30 минут
3 Формат выполнения код пишется на компьютере/бумаге по желанию, без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать знания стандартных структур данных и умение придумать и реализовывать необходимый алгоритм.

Ожидаемые вопросы:

  1. Можно ли добавить в структуру данных узла необходимое для работы этой функции поле?
  2. Можно ли выделить дополнительную память необходимого размера?
  3. Есть ли среди полей узла списка поле, содержащее заведомо уникальные данные?

Оценка результатов:

Очевидно, что лучшим решением будет то, которое основанно только на работе с указателями и связями списка без использования каких-то дополнительных средств, будь то выделение памяти или какие-то специфические предположения о данных.

 

Для начинающего программиста вопросы, связанные с использованием дополнительных допущений, приемлемы. Годится любое работоспособное решение. Лучше, если оно не основано на специфической структуре полей узла и предположениях о данных в этих полях. Хотя может, это и лучше, чем выделять дополнительно память под весь список?

 

От программиста с опытом мы не ожидаем вопросов, так как задача имеет решение для ситуации, когда на все приведенные вопросы дается отрицательный ответ.