Проверка, что список закольцован

запомни первый, и сравнивай с ним каждый следующий.

A -> B -> C -> D -> B

Так что не сработает.

http://en.wikipedia.org/wiki/Cycle_detection

Про лампочки и вагоны задачу слышал?

Воткни в структуру флаг "seen", скажем, так:

typedef struct __list_item{
  struct __list_item *prev;
  struct __list_item *next;
  sometype data;
  uint64_t flags;
...
} list_item;

#define FLAG_SEEN    1 << 0
#define FLAG_UNUSED  1 << 1
...
#define SOME_FLAG    1 << 63

далее при просмотре списка тебе придется проходиться по нему 2 раза: 1-й раз для обнуления FLAG_SEEN:

list_foreach_clear_flag(my_list, FLAG_SEEN); // понятно, что если возможна закольцованность, придется еще и содержать массив со списком членов списка

list_item *itm = my_list;
do{
  if(itm->flags & FLAG_SEEN) break; // itm->prev будет указывать на последний член кольца
  itm->flags |= FLAG_SEEN;
}while((itm = itm->next));

но намучишься ты с таким списком изрядно!

Спасибо, возьму зайца.

Нет

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

счетчик 1-байтовый, или 8-байтовый?

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

лучше не в массив, а в хеш

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

пустить 2 счетчика, один идёт поочередно, другой - через один. Если счетчики встретятся, то цикл.

если зацикливается не на первый, то не сработает.

если зацикливается не на первый, то не сработает.

Вопрос звучал «закольцован». Для кольца - сработает.

Да.

`1 -> 2 -> 3 -> 2 -> ..`  — имхо попадает под определение закольцован.

`1 -> 2 -> 3 -> 2 -> ..` — имхо попадает под определение закольцован.

Ты и ТС почему-то называете кольцом то, что является графом с циклом. Хотя... понятно, почему.

метод бегунка

ну к алгебраической структуре с операциями обратимного сложения и умножения это явно не относится. Так же раз разговор про список, то имеется ввиду структура данных double/single linked list. Граф это «модель» описывающая данную стуктуру данных. Так что иди умничай в другой тред, пожалуйста, тем более у тебя это не очень получается. Спасибо.

ну к алгебраической структуре с операциями обратимного сложения и умножения это явно не относится. Так же раз разговор про список, то имеется ввиду структура данных double/single linked list.

Именно так. И «кольцевым списком» обычно называется вот это:

Circular list

In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case the list is said to be 'circular' or 'circularly linked'

Так что иди умничай в другой тред, пожалуйста

Ответ ТС уже дан, умничаешь ты, спасибо.

ok.

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

На первом проходе нельзя определить, когда нужно остановиться. Если хранить множество всех посещённых вершин, то смысла делать два прохода нету.

Читай комментарий:

придется еще и содержать массив со списком членов списка

В принципе, можно и так сделать: изначально этот флаг держать нулевым, а при проверке на закольцованность после выявления закольцованности/незакольцованности опять вернуться к началу списка и пройтись, сбрасывая флаг.

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

google://задача про зайца и черепаху

Что-то вроде

list_item *itm = my_list, *circle_start = NULL;
do{
  if(itm->flags & FLAG_SEEN){
    circle_start = itm;
    break;
  }
  itm->flags |= FLAG_SEEN;
}while((itm = itm->next));
do{itm->flags &= ~FLAG_SEEN;}while((itm = itm->prev));

В итоге если есть закольцованность, circle_start будет указывать на один из членов кольца. Если нет — будет NULL.

Если нужно лишь диагностировать закольцованность и пофиг на лишние операции, можно сделать так: хранить в списке еще и общее количество членов, N. Затем пройтись по списку N-1 раз: itm = itm->next. Если у последнего itm->next будет !NULL, список точно закольцован!

тыц

А чтобы изначально сбросить у всех элементов FLAG_SEEN, нужно сделать проход. Который не закончится из-за цикла! А если мы сделали, чтобы он заканчивался, то значит задача уже решена, и мы придумали бесполезный алгоритм.

Не нужно: calloc сразу сделает с пустыми флагами, когда будешь очередной элемент в список добавлять.

Проблема надумана.

Твое решение требует модификации изначальной структуры данных. Есть более чистое решение.

Решение называется алгоритм Госпера, в гугле есть, или например в Алгоритмических трюках для программистов Уоррена.

Вообще, задачу решали много кто - Флойд, Кнут, Брент, Седжвик, Шиманский, Ниваш - и опубликовали результаты, а вот про алгоритм Госпера мало известно, хотя он довольно эффективный.

Без модификации элементов последовательности/списка это не очень простая задача.

Это кстати, алгоритм Флойда. Он находит такое n, при котором a[n]=a[2n]. Если это произошло, то период T есть, и он делит n.