линейный односвязный список 0

Et cetera → Программирование

Any_Key написал 19 января 2006 года в 17:38 (1135 просмотров) Ведет себя как мужчина; открыл 31 тему в форуме, оставил 325 комментариев на сайте.

Мой друг мне загадку загадал.

Есть линейный односвязный список и надо найти N-ый элемент с конца.

Несколько одгадок у меня есть, интересно что у вас.

Ответить Цитировать

Uncle Theodore 19:42, 19 января 2006

Метод называется «вагон и маленькая тележка».

Вагон едет, пока не упрется в конец, маленькая тележка отстает от него ровно на N элементов (как только это становится возможно). Как только вагон уперся в конец, в тележке — N-тый элемент с конца.

Подробно: Вагон поехал с начала. Счетчик щелкает. Как нащелкал N — поехала тележка, тоже с начала. На каждом шагу вагон продвигается на один элемент, и тележка на один элемент. Как вагон уперся — считываем содержимое тележки.

Good Luck,