Какие проверки нужны для проверки корректности связанного списка с циклом?

Что проверяют

Знаете ли вы, как вообще находят цикл в списке, и умеете ли думать о тестовых данных для алгоритма, а не только об интерфейсе. Следом обычно просят назвать минимальный набор входов, который ловит типичные ошибки реализации, или найти узел, с которого цикл начинается.

Как отвечать

Коротко про саму проверку. Классический способ это алгоритм Флойда, «черепаха и заяц»: один указатель идёт на шаг, другой на два. Если они встретились, цикл есть, если быстрый дошёл до null, цикла нет. Время O(n), память O(1). Альтернатива это множество посещённых узлов: проще, но требует O(n) памяти.

Дальше главное, набор тестов:

• пустой список: голова null, функция отвечает «цикла нет» и не падает;
• один узел без цикла и один узел, ссылающийся на себя: здесь ломается проверка fast != null && fast.next != null;
• два узла с циклом: минимальный настоящий цикл, проверяет условие встречи;
• цикл на голову, цикл в середине, хвост ссылается на предпоследний узел: разные точки входа в цикл;
• длинный список без цикла: чётная и нечётная длина, потому что быстрый указатель по-разному доходит до конца;
• большой список, сотни тысяч узлов: рекурсивная реализация может упасть с переполнением стека, а хеш-множество съесть память.

Удобно строить данные как массив узлов плюс индекс pos, куда ссылается хвост, где -1 значит «цикла нет». Каждый тест ставьте с таймаутом (@Timeout в JUnit 5, pytest-timeout в Python): ошибка в поиске цикла чаще всего выглядит как зависание, а не как неверный ответ.

Где спотыкаются

Предлагают «посчитать длину и сравнить». В списке с циклом подсчёт никогда не закончится, это и есть баг, который надо поймать.

Забывают про список из одного узла, который указывает сам на себя. На нём ломается большинство самописных реализаций.

Не проверяют, что функция не меняет список. Некоторые решения помечают посещённые узлы или разрывают ссылки, и после проверки структура уже испорчена.