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

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

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

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

Можно здесь поподробнее?

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

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

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

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

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

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

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

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

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

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

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 верен, но мой друг объяснил мне решение.