Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Задача по LinkedList / 19 сообщений из 19, страница 1 из 1
03.02.2014, 22:15
    #38547822
xml2015
xml2015
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
Задали тут на собеседовании такое задание:
Есть структура данных на подобии LinkedList'a, только односвязного. Т.е. имеющего ссылку next, такого же типа на элемент впередистоящий. Соответственно в случае последнего элемента next == null;
Предположим, что один из элементов ссылается на элемент, находящийся сзади. Таким образом при итерации получаем бесконечный цикл.
Написать алгоритм, определяющий бесконечный ли это список или нет.

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

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

например у вас массив интежеров, засовываем в linked list мапу как один элемент листа. ключ - интежер, а значение boolean равное false. во время прохождения по элементу делаем boolean true. если пришли, а он true - значит уже цикл
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2014, 09:50
    #38548101
AYTereschenko
AYTereschenko
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
Берем два указателя на начало списка и начинаем проходить по нему: один указатель движется с шагом 1, второй - с шагом 2. Если эти указатели когда-нибудь встретятся (будут указывать на один и тот же элемент), значит мы нашли цикл в списке. Если второй указатель дошел до конца списка, то циклов в нем нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2014, 10:05
    #38548124
0FD
0FD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
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:08
    #38548127
Сергей Арсеньев
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
cdtyjv Если цикл где-то в центре, то вы никогда не вернетесь в начало,
Для начала представьте себе цикл где-то в центре односвязанного списка .
А потом внимательно прочтите алгоритм. Тан написано же про "переворачивание связей".
Понятно, что при этом список портится и алгоритм надо прогнать еще раз для его восстановления (если это нужно).
Ну и это нифига не потокобезопасно. :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2014, 10:13
    #38548135
Zukora
Zukora
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
AYTereschenko,
Если "зацикленный" элемент непарный, к примеру 3, то цикл с шагом 2 дойдет до конца, цикл 1 нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2014, 10:19
    #38548147
ivanra
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
ZukoraAYTereschenko,
Если "зацикленный" элемент непарный, к примеру 3, то цикл с шагом 2 дойдет до конца, цикл 1 нет.
Алгоритм на самом деле правильный, но если волнуют циклы длиной 1, то достаточно добавиить проверку next!=this
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.02.2014, 10:26
    #38548158
Сергей Арсеньев
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача по LinkedList
Zukoraто цикл с шагом 2 дойдет до конца
До конца кольца?

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


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