Этот вопрос немного отличается от поиска пересечения двух связанных списков.
Рассмотрим связанный список с циклом: A - B - C - D - E - F - C.
Если узел A является входом для функции, он должен вернуть C.
Поскольку я не знаю, как называть C, я использовал термин петлевой узел C, как видно из вопроса. Хотя термин O (n 2) кажется очевидным, есть ли способ найти узел цикла с меньшей сложностью?
Хеш-таблица / дополнительное пространство O (n) не допускается.
Существует простой подход с использованием двух указателей: первый указатель увеличивается на единицу, а второй - вдвое быстрее, чем медленный указатель.
Итак, связанный список в вашем случае на самом деле A->B->C->D->E->F->C, что означает, что F снова указывает на C. Итак, подход похож на ниже
1. Продолжайте увеличивать два pointers до тех пор, пока они не совпадут. Таким образом, в приведенном выше случае у нас будет этот набор шагов
Медленный указатель: A B C D E
Быстрый указатель: A C E C E
Итак, мы останавливаемся на E, что указывает на наличие цикла. Теперь нам нужно найти узел цикла.
Теперь от E переместите медленный указатель в начало связанного списка и создайте новый указатель, который указывает на E и также увеличивается на 1. Точка, в которой встречаются эти два указателя, на самом деле является узлом цикла.
Указатель с начала: A B C Новый указатель: E F C
Итак, как вы видите, они встречаются в точке C, и мы закончили поиск узла цикла в связанном списке.
Обновление. Чтобы получить математическое подтверждение этого подхода, обратитесь к этому замечательному вопросу и посмотрите ответ @Jim Lewis вместе со всеми комментариями под ответом. Объясните, как найти узел начала цикла в связанном списке цикла работать?
Алгоритм поиска циклов Флойда является самым простым и часто является "каноническим ответом", потому что он то, что все изучают в университете (возможно, потому, что это просто, элегантно и проницательно).
Также часто утверждается, что среду выполнения нельзя улучшить, но это не так - большое Oh не может быть улучшено, но это только говорит нам кое-что об асимптотическом поведении в худшем случае. алгоритм Брента на практике работает быстрее, хотя при этом используется постоянный объем пространства. Есть и другие алгоритмы, такие как Gosper Loop Detection или Sedgewick, Szymanski и алгоритм Яо или k-stacks алгоритм, которые используют определенный (небольшой, но не постоянный в теории) объем пространства. Фактически, количество места будет по-прежнему постоянным для любой практической реализации связанных списков, потому что ваши указатели будут иметь фиксированный размер. Например, с 32-битными указателями Gosper's Loop Detection будет использовать 33 слова пробела (плюс, возможно, пара дополнительных, в зависимости от того, что вы хотите подсчитать).
Алгоритм Флойда хорош, но не обязательно. Ответ (tm). Есть выбор и компромиссы.
