Как стать автором
Обновить

Комментарии 23

Кажется так:
Проходим по списку и делаем две операции: считаем кол-во нодов и разворачиваем поинтеры в обратную сторону.

0-->0--> ===> 0<--0<-- // разворачивание, другого слова не нашел :)

Таким образом, если мы доходим до начальной точки, то список закольцован. Снова проходим сначала списка и разворачиваем поинтеры и считаем, как дойдем до первого, не развернутого поинтера, то значит дошли до цикла.
Отнимаем второе число из первого и получаем кол-во нодов в цикле. Продолжаем разворачивать поинтеры, дабы вернуть список в первоначальное состояние.

пи.си. кажись сложно будет понять, без рисунка.
а если список двусвязный?
в данном случае развернуть поинтеры не рекурсивно будет довольно проблемно.
Если список двухсвязный, то решение такое же, только разворачивать ничего не надо. Типа идешь по next, если дошел до начала, то есть круг. Подсчет также тривиален.
просто и в случае односвязного разворичивать не нужно.
есть исходный список list *src, делаем list *tmp = src. в цикле во время обхода подсчитываем кл-во элементов. если tmp == src, значит список циклический, если tmp == NULL, значит нет.
:)
если он циклический, то вы застрянете в цикле, и до NULL не дойдете.
а также до src.
кто вам такое сказал?
если заведомо известно, что src суть началос списка, то данный вариант работоспособен.
(0)-->(1)-->(2)-->(3)-->(4)-->(5)

Представте себе, что (5)-->(2)
попав в цикл, вы будете блуждать в нем..
А как определить что поинтер "неразвернутый"?
начальный лист:

(0)-->(1)-->(2)-->(3)-->(4)-->(5) + (5)-->(2)

после прохождения:

(0)(5)

(2)-->(5) это и есть не развернутый поинтер, тот который не нужно разворачивать, чтобы попасть куда-то.
баг какой-то, не дает развернуть стрелки.. Все поинтеры от 0 до 5 идут в обратном порядке, и только (2)-->(5) в другом.
Правильно ли я понял, что "неразворот" определяется по тому, что за "меньшим" (2) следует "больший" (5)? Если так, то видимо я не очень корректно поставил условие задачи. Как я уже заметил в http://www.habrahabr.ru/blog/sport_progr…
над элементами списка порядок не определен, поэтому сказать что (2) меньше (5) нельзя. Фактически есть только указатели, а как их там нам менеджер памяти раздал, в каком порядке - неизвестно.

list *tmp = source_list, *prev = NULL;
int i = 0, cyclic = 0;


for(;;) {
if(tmp == NULL) {
cyclic = 1;
break;
}
if((i > 0) && (tmp == source_list)) {
break;
}

i++;
tmp = tmp->next;
}

if(cyclic)
printf("Nodes number in the cyclic list is %d\n", i);
else
printf("This list was not cyclic one.\n");
чёрт, здесь prev не нужен =)
и естесвенно в первом ифе в цикле cyclic = 0, а во втором = 1.
p/s когда же я научусь проверять комментарии перед отправкой? =)
Да, моя ошибка, список конечно не закольцованый, а просто имеющий цикл. То есть 1, 2, и так далее, i элементы в цикле могут не состоять.
Наверное, можно сделать так. Начинаем идти с первого элемента двумя указателями. Один - с шагом 2, другой - с шагом 3. Если есть цикл то второй в какой-то момент догонит первого (НОД(2, 3) = 1). Тогда элемент, в котором догнали, входит в цикл. Ну и все, пройдем по циклу один раз, считая элементы.

Псевдокод:



p1 = begin, p2 = begin;

while (p1 != p2) {
p1 += 2, p2 += 3;
if (кто-то вылез за границу) - цикла нет.
}
int length = 1;
p2++;
while (p1 != p2) {
p2++;
length++;
}
length - ответ



Решение неоптимально (не использует изменяемость списка, будет сделано в худшем случае несколько проходов (штук 6, что ли)), но все равно за O(n).. Пока ничего лучшего мне в голову не приходит.
А, ну разумеется, количество проходов можно сократить (первый указатель - +1; второй - (+1 - сравнили с первым, +1 - сравнили), но со временем я погорячился - будет длина цикла + длина "предцикла" + еще один лишний проход по циклу для подсчета. Можно ли избавиться от этого прохода (как-то поменяв список), мне не очевидно :).
Подходит. А если теперь необходимо найти еще и длину "предцикла"?
Первое, что приходит в голову - один указатель бегает по циклу, другой идет от начала. Второй сделал шаг - первый оббежал весь цикл. Не встретились - второй опять делает шаг. Но длина цикла*длина начала - наверное, долго. Еще подумаю ;).
А что имеется в виду под изменяемостью списка? Значения в узлах или порядок соединения элементов? И какие операции разрешены над элементами списка? Только сравнение на равенство, или, например, на них определен порядок?
Список изменяем полностью, но не надо забывать, что в конце надо вернуть его в изначальное состояние. И нету никакой информации что именно хранится в списке и хранится ли что-нибудь вообще(кроме указателя на следующий элемент). Сравнение на равенство разрешено, порядок на них не определен.
Забавно:, с 2007 года никто не предложил полного решения.

Мне начинает приходить в голову, что в общем случае без использования дополнительных данных это невозможно, ибо нет признака посещённости.
По-хорошему, я бы предложил обходить такой список как дерево: через добавление чёрно-серо-белой окраски элементов.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории