Известный боян.Есть односвязный список. Нужно определить, замыкается ли он.
НЕВОЗМОЖНО
я так понимаю, решение в O(N²) не считается?
да, не считается. O(N).
а вообще, для этого в классе элемента списка делается отдельный маркер, который и указывает, проверен ли уже элемент или нет
ок. а теперь без маркеров.
скажем так, за константную память.
а проверка p→next == list.head чем плоха? Условие задачи неполное, или же задача тривиальна.
а кто сказал, что замыкаться может только в голову?
замыкаться он может куда угодно. типа в середину.
ok бгг, а проверка всех p→next на null? Или список может быть глючным?
че? наверное нет.
ну если в списке все ссылки на next не null, значит он замыкается.
как ты поймёшь, что все ссылки на next не null?
два итератора, один ходит на два элемента за раз, другой — на один. если вдруг окажутся равны на каком-то шаге — значит список замкнут
отныне я эникейщик
ты знал
я её решил за время примерное равное времени написания этих двух реплаев, году эдак в 2008м
прикольно
крут, че. а меня дважды подловили на подобных задачках. одна еще была про "столкнуть два программируемых паровозика", где под столкнуть подразумевалось также что один другого догонит) не догадался ни в один из разов.
реквестирую больше таких головоломок :)
http://cm.baylor.edu/ICPCWiki/Wiki.jsp?p...
Я тоже примерно тогда.
http://sim0nsays.livejournal.com/tag/pro...
23 comments
recommend
bookmark
subscribe
НЕВОЗМОЖНО
я так понимаю, решение в O(N²) не считается?
да, не считается. O(N).
а вообще, для этого в классе элемента списка делается отдельный маркер, который и указывает, проверен ли уже элемент или нет
ок. а теперь без маркеров.
скажем так, за константную память.
а проверка p→next == list.head чем плоха? Условие задачи неполное, или же задача тривиальна.
а кто сказал, что замыкаться может только в голову?
замыкаться он может куда угодно. типа в середину.
ok бгг, а проверка всех p→next на null? Или список может быть глючным?
че? наверное нет.
ну если в списке все ссылки на next не null, значит он замыкается.
как ты поймёшь, что все ссылки на next не null?
два итератора, один ходит на два элемента за раз, другой — на один. если вдруг окажутся равны на каком-то шаге — значит список замкнут
отныне я эникейщик
ты знал
я её решил за время примерное равное времени написания этих двух реплаев, году эдак в 2008м
прикольно
крут, че. а меня дважды подловили на подобных задачках. одна еще была про "столкнуть два программируемых паровозика", где под столкнуть подразумевалось также что один другого догонит) не догадался ни в один из разов.
реквестирую больше таких головоломок :)
http://cm.baylor.edu/ICPCWiki/Wiki.jsp?p...
Я тоже примерно тогда.
http://sim0nsays.livejournal.com/tag/pro...