Найти последний узел кругового связанного списка, размер которого неизвестен, а последний узел указывает на любой другой узел, кроме первого узла связанного списка

Question

Как найти последний узел кругового связанного списка, размер которого я не знаю, и последний узел указывает на любой другой узел, кроме первого узла связанного списка?

Answer 1

Один алгоритм, который можно использовать для этого, - это алгоритм цикла Флойда.

Также см. этот вопрос.

Answer 2

По определению, если узел не указывает на первый узел кругового связного списка,
это не последний узел.

Не могли бы вы уточнить здесь?

Answer 3

Странный список ... зачем вам что-то подобное? Но все равно ...

Вы можете просто перебрать все узлы и остановиться, как только следующий узел будет тем, который вы уже посетили. Текущий узел будет вашим ответом.

Вам нужен какой-то способ отслеживать, какие узлы были посещены. Добавьте логический флаг к каждому узлу или используйте какой-либо тип данных набора с быстрой вставкой и поиском (например, хэш-набор).

Answer 4

Я могу подробно рассказать, как использовать алгоритм Флойда для решения этой проблемы, но я не понимаю объяснения одного шага

1. Имеют 2 указателя, пересекающих связанный список, указатель 1 идет со скоростью 1 узел за итерацию, второй - со скоростью 2 узла
2. Когда указатели встречаются, мы находимся в цикле, и мы находимся на некотором расстоянии, прежде чем указатель 1 достигнет конца цикла (мы знаем, что указатель 1 не достиг, то конец, потому что если цикл равен расстоянию d и указатель 2 идет при удвоенной скорости 1 указатель1 будет повторять цикл дважды, прежде чем указатель 1 сделает это один раз)
3. Так как они встретились до того, как указатель 1 полностью прошел цикл, мы знаем, что точкой встречи является d узлов от начала и k узлов в цикле (pos = d + k)
4. Если мы установим указатель 1 в положение 0 и снова запустим обе точки (но с одинаковой скоростью 1 узел на одну итерацию), они встретятся в начале цикла.
5. Поскольку мы знаем начало цикла, найти конец тривиально

Я не совсем понимаю, почему шаг 4 верен, но у меня был друг, который объяснил мне решение.

Answer 5

Алгоритм цикла Флойда не даст последний элемент списка. Он только скажет, есть ли цикл или нет.

Определение последнего будет таким: при прохождении списка при последовательном сканировании, начиная с первого, все элементы перед ним и последний не будут видны раньше (значение указателя). После последнего будет первый элемент, который уже был замечен в этом последовательном сканировании.

Простое решение - пометить посещенные элементы, чтобы элемент, который уже виден, был легко обнаружен. Флаг может быть навязчивым, то есть путем изменения бита в элементе, или внешним, используя хеш-таблицу для хранения значений указателя.

Поскольку нам нужно проверить, был ли элемент уже посещен, другого решения я не вижу.

Answer 6

Может быть, добавить параметр к узлам списка, который говорит вам, если вы в конце? Я думаю, это не будет проблемой.

В противном случае вы можете запомнить узлы, которые вы уже просматривали. Когда следующий узел уже посещен, вы находитесь в конце.