А где конец?

[chur]

Можно определить какую-нибудь хеш-функцию и сравнивать не со всеми предыдущими элементами, а только с частью.
Но это, ИМХО, уход от борьбы.

[Eugie]

А может так?

Алгоритм в два прохода. На первом в каждом элементе зануляем указатели на следующий, предварительно сохраняя их в массиве. Таким образом проходим весь список пока не достигнем элемента с next = NULL (не зацикливаясь!) и подсчитываем количество элементов в списке (или + 1, если список зациклен). Затем повторно проходим по элементам, беря адреса из массива и восстанавливаем список, декрементируя счетчик. Когда в счетчике будет 0, смотрим, что записано в поле next: если не NULL - список зациклен.

Должно работать

[Naeel Maqsudov]

Хорошее решение (оно восходит к идее "здесь был Вася"), но есть есще мысль:

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

[Hawk]

Эх это все понятно, но было решение без использования бополнительной памяти и без торможений на каждом проходе.

[Naeel Maqsudov]

А список двусвязный или односвязный?

[Hawk]

Односвязный

[Hawk]

Во !!! Нашел, точнее люди просветили. Гениально =)
Надо запустить по списку 2 указателя, один по каждому элементу идет, а второй по двум, и сравнивать их каждый раз друг с другом. Если не зацикленный список, рано или поздно один из указателей (скорее быстрый) наткнется на NULL, а если зацикленный, то быстрый указатель нагонит в конце концов медленный и они окажутся равны

[Eugie]

Изящное решение. Чувствуется за ним этакий физический склад ума

[Andragen]

Знакомая задачка
Нам препод когдато задал, кто решит томого от экзамена с 10 освобождает
В группе из 40 человек решил только я ,сдесь предоставленно решение при помощи реверсирования(перевое которое пришло мне в голову),но есть и другие методы, на сколько я помню я потом ещё до двух допёр,
Вот решение

Код: Выделить всё

#include<stdio.h>
#include<conio.h>
enum bool {true=1, false=0};//opredeliaem bolevii tip

struct Item //struktura opisivaiushiaia element spiska
 {int elem;//element spiska
  Item *next;//ukazateli na sleduiushii Item
  Item(int cis){elem=cis;}//konstruktor
 };

typedef Item *link;

//vozrahiet true esli iz elementa 'iz' dostupen 'el' i false v obratnom sluciae
bool ifdostijim(link iz, link el)
 {
  Item *y=iz;

  while(y!=NULL)
    {if(y==el)return true;//proveriaet esli adres 'iz'  raven adresu 'el'
     y=y->next;
    }
    return false;//vozrasiaem false esli element ne naiden
 }


//reversiruem spisok i proveriaem esli posleduiushi element dostupen iz
//uje otreversirovanogo spiska, esli dostupen togda esti kolitso
//vozrashiaet true esli esti kolitso i false v obratnom sluciae
bool reversering(link &beg)
 {link t,y=beg,r=NULL;
   while(y!=NULL)
     {t=y->next;
      y->next=r;
      r=y;
	if(ifdostijim(y,t))
	 { beg=y;
	 return true;
	 }
      y=t;
     }
     beg=r;
     return false;
 }

 //meniu
void Meniu()
     {printf("%43s","MENIU");
      printf("\n0)Vihod(Esc)");
      printf("\n1)Proverka spiska a");
      printf("\n2)Proverka spiska b");
     }


void press()
     {
     printf("\nPress any key to continue...");
     getch();
     }


 //nacialo programmi
 void main()
    {//opredeliem spisok s ciklom
     Item a1(1),a2(2),a3(3),a4(4),a5(5),a6(6),*abeg;
     //delaem sviazi i zatsiklivem 6 i 3 elementi
     abeg=&a1;
     a1.next=&a2;
     a2.next=&a3;
     a3.next=&a4;
     a4.next=&a5;
     a5.next=&a6;
     a6.next=&a3;
     //opredelim spisok bez tsikla
     Item b1(1),b2(2),b3(3),b4(4),b5(5),b6(6),*bbeg;
     //delaem sviazi i 6 element ukazivaet v NULL
     bbeg=&b1;
     b1.next=&b2;
     b2.next=&b3;
     b3.next=&b4;
     b4.next=&b5;
     b5.next=&b6;
     b6.next=NULL;

     char men=0;

     do{clrscr();
	Meniu();
	men=getch();
	 switch(men){
		     case '1':clrscr();
			      if(reversering(abeg))
			      printf("Spisok bill zacolitsovan");
			      else printf("Spisok ne zakolitsovan");
			      press();
			      break;
		     case '2':clrscr();
			      if(reversering(bbeg))
			      printf("Spisok bill zacolitsovan");
			      else printf("Spisok ne zakolitsovan");
			      press();
			      break;
		    }

       }while(!(men=='0'|| men==27));

       clrscr();
       printf("Press any key to exit...");
       getch();

    }