Алгоритм Заяц и Черепаха
Принцип достаточно прост - делаем два указателя и пускаем их по списку с разной скоростью. Первый медленный или черепаха идет по каждому узлу списка, а второй, быстрый Заяц - скачет через один.
Что из этого можно получить?
В магию математики погружаться не будем...
1. Найти середину списка
Если заяц доскакал до конца, то черепаха будет как раз на середине. Красота!
Возвращаем указатель "черепаха" вот вам и решение задачи.
2. Определить цикличен список или нет?
Опять запускаем наших животных и ждем когда они встретятся. А они точно встретятся (магия математики).
Т.е. если последний узел зациклен на любой из узлов списка, то заяц обязательно войдет в цикл и догонит черепаху.
И вот если два указателя показывают на одно и то же место, то список однозначно зациклен.
3. Определить начала цикла.
Если наш список зациклен, то исходя их пункта 2 мы можем узнать где "встретились" черепаха и заяц.
А дальше опять магия, если начать движение по каждому следующему узлу от головы списка и от точки встречи, то точка пересечения, т.е. когда оба указателя дойдут до одного узла, то этот узел и будет первым узлом цикла.
Не верите, проверьте! Магия работает!!!
4. Определить последний элемент замкнутого списка
Ну тут совсем просто, нашли первый узел цикла, и топаем дальше пока не найдем узел который на него ссылается. Вот вам и последний элемент.
И еще парочка задач, когда дано два списка
1. Узнать пересекаются они или нет?
Тут сначала проходим эти списки до конца, если конец один и тот же элемент значит пересекаются.
2. Если пресекаются, то где?
А тут опять магия, берем "хвост" и зацикливаем его на одну из голов.
А со второй ищем первую точку цикла - которая и есть точка пересечения.
Только после не забывайте убрать цикл с хвоста, что бы чего не вышло...