Здравствуйте, Жмур, Вы писали:


Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
Ж>применять дополнительные средства, типа создать карту элементов, чтобы потом
Ж>проверить повторно встречающийся элемент, нельзя.

Ж>Оформить это нужно не в виде языка, а показать на пальцах.

Ну если на пальцах, то вот более рациональное и соответсвующее условию, имхо, решение, чем то что приводил Flamer. Его решение находит только закольцован список или нет. Потом еще дополнительно нужно будет искать последний элемент.

Я опущу проверку на закольцованость, которую добавить не трудно (понадобятся: память на хранение адреса первого элемента и пара if-ов), тем более что в условии ясно сказано что список закольцован. Сделаем так: будем идти по списку и менять направление ссылок на обратное, при этом первый элемент сошлем на "нулевой". При этом будем вести счетчик пройденых элементов списка.

То есть, если начальный список будет такой:

a -> b -> c -> d -> e -> f -> c

То после нескольких итераций он станет таким(при этом мы сейчас рассматриваем пару элементов d-e):

a <- b <- c <- d -> e -> f -> c

Дойдя до "конца" списка получим:

a <- b <- c <- d <- e <- f -> c

После чего продолжаем идти по ссылкам и менять их на "противоположные". Дойдя до начала(то есть элемента который ссылается на "нулевой элемент") мы получим такую структуру:

a -> b -> c <- d <- e <- f <- c

Вот тут, кстати говоря, и нужно, если что сделать проверку на закольцованость: достаточно сравнить адреса пары элементов: ссылющегося на "нулевой" элемент и начального, сохраненного нами в самом начале. Если совпадают — закольцован, нет — линеен.
Заметим, что после данного прохода в счетчике мы получили некое число, которое, если разобратся, равно 2k+p, где p-кол-во элементов в цикле, а к-кол-во элементов не входящих в цикл. Обозначим его C(count). После этого пройдем по списку C шагов не меняя ничего. При этом мы окажемся где-то внутри цикла. После этого нам осталось запомнить адрес текужего элемента и пройтись полностью по циклу — до попадания на этот же элемент, при этом подсчитывая шаги в новом счетчике. Мы получили p. Теперь совсем не сложно вычислить k=(c-p)/2. Теперь мы знаем номер элемента(если считать от начала), который "начинает" список. Также у нас есть адрес первого элемента — так что найти нужный нам элемент труда не состовляет.

Вот и все. На все про все понадобилось 2*(2*k+p)+p шагов, а также несколько дополнительных байт памяти.