ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Задача по LinkedList
19 сообщений из 19, страница 1 из 1
Задача по LinkedList
    #38547822
xml2015
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xml2015
Гость
Задали тут на собеседовании такое задание:
Есть структура данных на подобии LinkedList'a, только односвязного. Т.е. имеющего ссылку next, такого же типа на элемент впередистоящий. Соответственно в случае последнего элемента next == null;
Предположим, что один из элементов ссылается на элемент, находящийся сзади. Таким образом при итерации получаем бесконечный цикл.
Написать алгоритм, определяющий бесконечный ли это список или нет.

Ваше решение(кому интересно разумеется)?
...
Рейтинг: 0 / 0
03.02.2014, 22:15
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38547842
Лагман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лагман
Участник
При переборе меняем порядок списка , в итоге если вернулись к началу - то бесконечный.
...
Рейтинг: 0 / 0
03.02.2014, 22:36
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38547940
elitegroup
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
elitegroup
Гость
Если у списка можно получить размер, то я бы проверил так:
Код: java
1.
2.
3.
if (currentCountIteration > list.size()) {
   // вечный цикл... 
}
...
Рейтинг: 0 / 0
04.02.2014, 01:16
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548026
cdtyjv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cdtyjv
Участник
ЛагманПри переборе меняем порядок списка , в итоге если вернулись к началу - то бесконечный.Не катит. Если цикл где-то в центре, то вы никогда не вернетесь в начало, но список все равно будет бесконечным.
...
Рейтинг: 0 / 0
04.02.2014, 07:51
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548057
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ivanra
Гость
С помощью вспомогательного хешсета, если, конечно, задача допускает использование доп. памяти
...
Рейтинг: 0 / 0
04.02.2014, 09:09
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548089
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
redwhite90
Гость
xml2015Задали тут на собеседовании такое задание:
Есть структура данных на подобии LinkedList'a, только односвязного. Т.е. имеющего ссылку next, такого же типа на элемент впередистоящий. Соответственно в случае последнего элемента next == null;
Предположим, что один из элементов ссылается на элемент, находящийся сзади. Таким образом при итерации получаем бесконечный цикл.
Написать алгоритм, определяющий бесконечный ли это список или нет.

Ваше решение(кому интересно разумеется)?

например у вас массив интежеров, засовываем в linked list мапу как один элемент листа. ключ - интежер, а значение boolean равное false. во время прохождения по элементу делаем boolean true. если пришли, а он true - значит уже цикл
...
Рейтинг: 0 / 0
04.02.2014, 09:41
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548101
AYTereschenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AYTereschenko
Гость
Берем два указателя на начало списка и начинаем проходить по нему: один указатель движется с шагом 1, второй - с шагом 2. Если эти указатели когда-нибудь встретятся (будут указывать на один и тот же элемент), значит мы нашли цикл в списке. Если второй указатель дошел до конца списка, то циклов в нем нет.
...
Рейтинг: 0 / 0
04.02.2014, 09:50
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548124
0FD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
0FD
Участник
xml2015,

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
A first=...;
A next=first;
while(next!=null){
	A n=next.next;
	while(n!=null){
		if(n==next){
			System.out.println("Цикл");
                        return;
		}
		n=n.next;
	}
	next=next.next;
}
...
Рейтинг: 0 / 0
04.02.2014, 10:05
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548127
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
cdtyjv Если цикл где-то в центре, то вы никогда не вернетесь в начало,
Для начала представьте себе цикл где-то в центре односвязанного списка .
А потом внимательно прочтите алгоритм. Тан написано же про "переворачивание связей".
Понятно, что при этом список портится и алгоритм надо прогнать еще раз для его восстановления (если это нужно).
Ну и это нифига не потокобезопасно. :)
...
Рейтинг: 0 / 0
04.02.2014, 10:08
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548135
Фотография Zukora
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Zukora
Участник
AYTereschenko,
Если "зацикленный" элемент непарный, к примеру 3, то цикл с шагом 2 дойдет до конца, цикл 1 нет.
...
Рейтинг: 0 / 0
04.02.2014, 10:13
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548147
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ivanra
Гость
ZukoraAYTereschenko,
Если "зацикленный" элемент непарный, к примеру 3, то цикл с шагом 2 дойдет до конца, цикл 1 нет.
Алгоритм на самом деле правильный, но если волнуют циклы длиной 1, то достаточно добавиить проверку next!=this
...
Рейтинг: 0 / 0
04.02.2014, 10:19
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548158
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Zukoraто цикл с шагом 2 дойдет до конца
До конца кольца?

Если next().next() == null
, то и
a =next();
a.next()==null
...
Рейтинг: 0 / 0
04.02.2014, 10:26
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548164
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
ivanraАлгоритм на самом деле правильный, но если волнуют циклы длиной 1, то достаточно добавиить проверку next!=this
Не обязательно.
Если a.next()==a, то и a.next()==a.next().next()
...
Рейтинг: 0 / 0
04.02.2014, 10:30
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548243
Лагман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лагман
Участник
cdtyjvЛагманПри переборе меняем порядок списка , в итоге если вернулись к началу - то бесконечный.Не катит. Если цикл где-то в центре, то вы никогда не вернетесь в начало, но список все равно будет бесконечным. Почему это не вернусь. Вернусь обязательно.
...
Рейтинг: 0 / 0
04.02.2014, 11:34
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548264
cdtyjv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cdtyjv
Участник
ЛагманcdtyjvНе катит. Если цикл где-то в центре, то вы никогда не вернетесь в начало, но список все равно будет бесконечным. Почему это не вернусь. Вернусь обязательно.Да ладно, тут даже говорить об этом смысла нет, так как по условию задачи список односвязный, следовательно, вы не можете идти "назад".
...
Рейтинг: 0 / 0
04.02.2014, 11:47
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548277
cdtyjv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cdtyjv
Участник
На самом деле, хз о чем мы тут говорим, так как правильный ответ уже был дан AYTereschenko : http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
...
Рейтинг: 0 / 0
04.02.2014, 11:55
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548322
Лагман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лагман
Участник
cdtyjvЛагманпропущено...
Почему это не вернусь. Вернусь обязательно.Да ладно, тут даже говорить об этом смысла нет, так как по условию задачи список односвязный, следовательно, вы не можете идти "назад".
я же сказал что буду менять направление, т.е. переставлять линки в обратную сторону.
...
Рейтинг: 0 / 0
04.02.2014, 12:14
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548413
cdtyjv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
cdtyjv
Участник
Лагманя же сказал что буду менять направление, т.е. переставлять линки в обратную сторону.То есть вам надо менять список. Не подходит.
...
Рейтинг: 0 / 0
04.02.2014, 12:49
| Ответить | Цитировать | Написать  
Задача по LinkedList
    #38548453
Лагман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лагман
Участник
cdtyjvЛагманя же сказал что буду менять направление, т.е. переставлять линки в обратную сторону.То есть вам надо менять список. Не подходит.
ну ладно, ты победил )
...
Рейтинг: 0 / 0
04.02.2014, 13:03
| Ответить | Цитировать | Написать  
19 сообщений из 19, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Задача по LinkedList
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=38548453&tid=2127708]:
 0ms
get settings:
 9ms
get forum list:
 16ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 34ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 63ms
get tp. blocked users:
 2ms
others: 217ms
total:  366ms
созд. / загр.: 366ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]