К основному контенту

Занимательные алгоритмы. Поиск цикла в односвязном списке

И снова про тараканов, которые иногда возникают в голове. Как-то раз, засыпая, я задумался на курьезными задачками из своей сферы деятельности (Lotus Notes), которые можно было бы задать на собеседовании, плавно перешел к воспоминаниям о своих первых собеседования, когда опыта работы еще не было. Опыт самих собеседований у меня не велик а места, где задавались действительно интересные задачи (а не задачки типа: написать сортировку массива любым известным способом) вообще равны одному - это ABBYY. Как минимум одна задачка в списке на знание и понимание классических алгоритмов, описанных в книге Дональда КнутаИскусство программирования.

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

Задача: Дан однонаправленный список (указатель на его первый элемент). Определить, имеется ли в списке цикл за кол-во операций O(n), где n - кол-во элементов в списке и используемой дополнительной памяти О(1).

Ограничения, накладываемые условиями:
1. Кол-во элементов - n - конечно, но не известно;
2. Сравнение текущего "индекса" с n не возможно, исходя из п.1;
3. Сравнение каждого с каждым и использование других структур данных не возможно, исходя из условий по сложности и используемой памяти;
4. Нельзя изменять содержимого элемента списка.

Решение 1: 
Стандартный алгоритм, решающий данную задачу с указанными ограничениями основывается на двух указателях (p1 и p2), пускаемых по списку с шагом 1 и 2 элемента. Если в какой-то момент времени указатель p2 догонит p1 => цикл существует. Описание алгоритма и его доказательство рассматривается много где. Наверно наиболее подробно вопросы зацикливания рассмотрены тут.

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

Решение 2:
1. Будем идти по списку (сохранив указатель на первый элемент) и переворачивать указатели, образовывая обратный список
2. Если один прекрасный момент указатель на след. элемент будет не определен => цикла нет. Далее см. п. 4.
3. Если мы вернулись к изначальному указателю (на рисунках видно каким образом) => цикл есть. Далее см. п. 4.
4. Для возврата к исходному состоянию списка - пройдемся в обратном направлении, разворачивая указатели.


Итого будет выполнено не более 2n + 2n операций (если цикл на последних элементах), а исходя из определения, O(2n + 2n) = O(4n) = O(n). Количество необходимой памяти в каждый момент: указатель на первый элемент списка + 3 указателя на 3 последовательных элемента списка (для их корректного "разворота") => O(1 + 3) = O(4) = O(1). Вроде нигде ничего не напутал.

Контакты:

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Unit-testing object validation when validator has DI

Summary Unit test object validation when validator(s) has a dependency. For instance, we have some custom field and cross-field validators. Want to test their combination. Additionally some of validators have dependencies, injected through constructor or setters. You're not using property injection, right? Shortcut If you are just searching for an answer, here's the fast way: Declare CustomConstraintValidatorFactory that implements javax.validation.ConstraintValidatorFactory Override getInstance method and on facing your constraint validator class instantiate it Otherwise delegate validator construction to org.hibernate.validator.internal.engine.constraintvalidation.ConstraintValidatorFactoryImpl Build validator factory and provide it your CustomConstraintValidatorFactory Build validator, using that factory... Go to demo project on GitHub for details:  https://github.com/MrArtemAA/blog-demos/blob/master/test-validator-with-injection/src/test/java/ru/artemaa/d

Lotus Notes FAQ. 8/9 Eclipse. Как настроить уведомления о Sametime сообщениях

Н а написание данной "инструкцию" натолкнул мой коллега. Помню, первый раз сам долго искал, как отключить постоянно выпрыгивающие уведомления о новых сообщениях в Sametime. И так, речь идет о клиентах IBM Notes 8+ версии Standart (Eclipse based). Как настроить уведомления о Sametime сообщениях?