Всем доброго времени сУток!
Вопрос в следующем.
Есть двусвязный список:

Как(в теории) определить, закольцован он или нет?
Рекурсия не подходит. Сами понимаете почему.
В общем...любопытно Ваше мнение.

Спасибо за внимание.

берешь два итератора("быстрый" и "медленный" ), пускаешь их по кругу, где на два шага "быстрого" приходится один шаг "медленного"..
проверяешь оба итератора на равенство после каждого шага "быстрого", и если встретились раньше, чем "быстрый" дошел до конца, значит список закольцован.
  


Это сообщение отредактировал(а) mes - 12.4.2009, 21:33

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

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

ЗЫЖ к стенке надо таких прграммистов

Добавлено через 2 минуты и 9 секунд
2mes, 

а я там давал вторую часть задачи? починить список?

Третий не нужно - для проверки 2-х раз достаточно   


За что меня к стенке?    Я всего-лишь предложил 2 варианта - первый мне больше нравится.    Вашего варианта я же не видел - может он лучше, я бы свои не предлагал.

Злые вы.   

т.е. второй раз "случайно такое значение"(С)Anikmar быть не может? это закон природы такой, да?   


вы видели вариант mes'а, но видимо не прониклись

Добавлено через 47 секунд

мы не злые, мы мудрые

А если конец списка ссылается на начало? Быстрый итератор будет равен первому элементу, а медленный в середине где-то? Разве равенство сработает?


Второй раз случайно может быть, но это обнаружимо. В любом случае, я вижу только мой первый вариант как 100% 

Все проникся - все равно догонит.


Мудрые к стенке не ставят. Мудрые доводят до самоубийства.    

Это сообщение отредактировал(а) Anikmar - 13.4.2009, 09:45

Цитата(Anikmar @  13.4.2009,  06:30 )

Вашего варианта я же не видел - может он лучше, я бы свои не предлагал.

Предложенный мной вариант, был услышан некоторое время назад от Joker.   


припоминаю.. для односвязанного списка. 
Видится примерно такая картина:
от места встречи проходим по круг у и узнаем длину петли. 
и на основании длины петли, кол-во шагов быстрого итератора, и шагов медленного можно посчитать место пересечения.

Так для случая отн. большой петли (если быстрый до места встречи успел пройти по петле только раз) 
L=2*O-S , 
где L - длина от начала , до конца (до стыка который надо востанавливать)
      О-длина петли
      S-кол-во шагов медленного.

Для остальной части задачи надо мозги напрячь.. попозже попробую.. 
  

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

 если только список предполагал возможность окрашивания +  надо как то убедиться что список нигде не подкрашен.
  

Да. Этот вариант мне больше нравится.


И вернулись к изначальному вопросу  

и в чем проблема создать map<void*, isColored> подобную структуру при обходе? не вижу никаких проблем.

jonie, Да. Спасибо. Вопрос решен.

а как узнать длину списка если он закольцован ?
a если проверять есть ли в списке уже указатель, то зачем параметр isColored ?