связанный список

[leonid_v]

можно. но хвоста то нет есть кольцо

[Serge_Bliznykov]

какая занимательная задачка-головоломка! супер!

leonid_v, а скажите, можно ли предположить, что в списке не более чем X элементов (ну. например, в списке не более 1000 элементов (или 10000 или миллион - не суть важно)). Исходя из этого условия можно найти элемент, на который идёт зацикливание и далее уже задача решается элементарно!



кстати, а почему имя файла на иврите?

[leonid_v]

нет.в задаче не сказано

[Serge_Bliznykov]

тогда как вам такое решение.
предположим, что в списке K элементов (K-й элемент == концевому).
тогда конецевой элемент должен ссылаться на один иэ элементов, расположенный на протяжении от головы и до элемента K
так же предположим, что, сначала, K=1
проверим это предположение, если это не так, увеличим K на единицу и опять проверим. будем повторять до тех пор, пока условие не выполнится.
профит.

на псевдокоде это будет примерно так

  K := 1;
  начало цикла
     перебирая элементы от head найти K-й элемент списка.
     запомнить его в pEnd;
     перебирая элементы от head до K 
        сравнивать каждый элемент с pEnd^.Next 
                (if на него ссылается последний элемент),  тогда признак_готово :=  true) 
     если не признак_готово, тогда увеличить K на 1
повторять цикл до тех пор, пока не станет признак_готово

[leonid_v]

в условии сказано что время работы O(n) а это подразумевает нет цикла в цикле

[Helloween]

сохрани адрес первого элемента и беги пока он снова не встретится. Профит!
int fa = &l->first();
int count = 0;
do
{
count++;
}while(&l->next() != fa)

ну как нить так.
Если кольцо замыкается на первом элементе канешн.
Реализацию списка надо для начала увидеть, чтобы судить что к чему.

[Serge_Bliznykov]

Helloween, а вы иллюстрацию не смотрели?

позволю её продублировать:


ссылка идёт НЕ на первый элемент списка!

в условии сказано что время работы O(n) а это подразумевает нет цикла в цикле

ну да. в моём решении это условие явно не выполняется!
я в расстерянности...



.

[leonid_v]

я в расстерянности...:confuse d:

[Serge_Bliznykov]

скажу сейчас одну крамольную вещь...
только просьба помидорами не кидаться!

у каждого элемента в списке есть адрес (указатель). Если предположить, что элементы выделялись последовательно, то у лежащих правее элементов адрес (указатель) имеет большее значение, чем у тех элементов списка, что лежат левее.
улавливаете, к чему это я?
если указатель на следующий элемент больше, чем адрес самого элемента, значит этот элемент НЕ КОНЦЕВОЙ.


p.s. на самом деле, я бы категорически не рекомендовал использовать подобные "трюки" в реальной задаче - ибо это всё хакерсто, глюкодром и вообще КРАЙНЕ не надёжно!!!
просто я не вижу других вариантов решения задачи

[Stilet]

но хвоста то нет есть кольцо

Как это нет?
При добавлении в список можно проделать проход от добавленного элемента до конца списка или до элемента, равному добавленному. Так можно понять что на этом элементе петля.

Добавили элемент
Элемент = новый элемент
пока элемент.следующее не нуль или элемент не равен новый элемент
 элемент равен следующему
конец цикла
Если Элемент.следующее не равен нулю То это элемент петли