Скажем, у вас есть структура связанного списка в Java. Он состоит из узлов:
class Node {
Node next;
// some user data
}
и каждый узел указывает на следующий узел, за исключением последнего узла, который имеет нулевое значение для следующего. Скажем, есть вероятность, что список может содержать цикл - то есть конечный узел, вместо нуля, имеет ссылку на один из узлов в списке, который предшествовал ему.
Какой лучший способ написания
boolean hasLoop(Node first)
который вернется, true
если данный узел является первым из списка с циклом, и в false
противном случае? Как вы могли бы написать так, чтобы это занимало постоянное количество места и разумное количество времени?
Вот изображение того, как выглядит список с циклом:
java
algorithm
data-structures
linked-list
jjujuma
источник
источник
finite amount of space and a reasonable amount of time?
:)Ответы:
Вы можете использовать алгоритм нахождения цикла Флойда , также известный как алгоритм черепахи и зайца .
Идея состоит в том, чтобы иметь две ссылки на список и перемещать их с разной скоростью . Переместить один вперед на
1
узел, а другой на2
узлы.next
) станетnull
.Java-функция, реализующая алгоритм:
источник
fast.next
передnext
повторным вызовом :if(fast.next!=null)fast=fast.next.next;
Вот уточнение решения Fast / Slow, которое правильно обрабатывает списки нечетной длины и улучшает ясность.
источник
slow == fast.next
тогдаslow
будет равноfast
на следующей итерации; он сохраняет только одну итерацию максимум за счет дополнительного теста для каждой итерации.slow
не может стать нулевым,fast
поскольку он следует по тому же пути ссылок (если у вас нет одновременной модификации списка, в этом случае все ставки отключены).Лучше, чем алгоритм Флойда
Ричард Брент описал альтернативный алгоритм обнаружения цикла , который во многом похож на зайца и черепаху [цикл Флойд], за исключением того, что медленный узел здесь не перемещается, но позже «телепортируется» в положение быстрого узла при фиксированном интервалы.
Описание доступно здесь: http://www.siafoo.net/algorithm/11 Брент утверждает, что его алгоритм работает на 24–36% быстрее, чем алгоритм цикла Флойда. O (n) временная сложность, O (1) пространственная сложность.
источник
slow.next != null
? Насколько я вижуslow
, всегда позади или равноfast
.Альтернативное решение для Черепахи и Кролика, не совсем хорошее, так как я временно изменяю список:
Идея состоит в том, чтобы пройти список и повернуть его вспять, как вы идете. Затем, когда вы впервые достигнете узла, который уже был посещен, его следующий указатель будет указывать «назад», вызывая повторение итерации в направлении
first
, где она заканчивается.Тестовый код:
источник
Черепаха и заяц
Взгляните на алгоритм ро Полларда . Это не совсем та же проблема, но, возможно, вы поймете логику из нее и примените ее для связанных списков.
(если вам лень, вы можете просто проверить обнаружение цикла - проверьте часть о черепахе и зайце.)
Это требует только линейного времени и 2 дополнительных указателей.
В Java:
(Большинство решений не проверяют и то,
next
и другоеnext.next
на нули. Кроме того, поскольку черепаха всегда позади, вам не нужно проверять ее на ноль - заяц уже сделал это.)источник
У пользователя unicornaddict есть хороший алгоритм, описанный выше, но, к сожалению, он содержит ошибку для нецикличных списков нечетной длины> = 3. Проблема в том, что он
fast
может «застрять» непосредственно перед концом списка,slow
догоняет его и петля (ошибочно) обнаружена.Вот исправленный алгоритм.
источник
В этом контексте есть множество текстовых материалов повсюду. Я просто хотел опубликовать схематическое представление, которое действительно помогло мне понять концепцию.
Когда быстро и медленно встречаются в точке р,
Расстояние, пройденное быстро = a + b + c + b = a + 2b + c
Расстояние, пройденное медленным = a + b
Так как быстрый в 2 раза быстрее, чем медленный. Таким образом, a + 2b + c = 2 (a + b) , тогда мы получаем a = c .
Поэтому, когда другой медленный указатель снова запускается из головы в q , в то же время быстрый указатель будет бегать от p до q , поэтому они встречаются в точке q вместе.
источник
a
он больше, чем длина цикла, тогда fast сделает несколько циклов, и формулаdistance (fast) = a + b + b + c
изменится наa + (b+c) * k + b
введение дополнительного параметра,k
который подсчитывает количество циклов, выполненных fast.Алгоритм
сложность
источник
n
исправленоequals
иhashCode
. Это не одно и то же. И это разыменовываетnull
по последнему элементу. И вопрос ничего не сказал о хранении узлов вLinkedList
.Следующее, возможно, не лучший метод - это O (n ^ 2). Тем не менее, это должно послужить выполнению работы (в конце концов).
источник
Прости меня за мое невежество (я все еще довольно новичок в Java и программировании), но почему вышеперечисленное не работает?
Я думаю, что это не решает проблему постоянного пространства ... но это, по крайней мере, добирается туда за разумное время, правильно? Он займет только пространство связанного списка плюс пространство набора с n элементами (где n - количество элементов в связанном списке или количество элементов, пока он не достигнет цикла). И на время анализ наихудшего случая, я думаю, предложил бы O (nlog (n)). SortedSet ищет для содержащегося () лога (n) (проверьте javadoc, но я уверен, что базовой структурой TreeSet является TreeMap, чье дерево, в свою очередь, красно-черное), и в худшем случае (без циклов, или цикл в самом конце), он должен будет сделать n поиска.
источник
Если бы нам было разрешено встраивать класс
Node
, я бы решил проблему, как я это реализовал ниже.hasLoop()
работает за O (n) времени и занимает только пространствоcounter
. Это кажется подходящим решением? Или есть способ сделать это без встраиванияNode
? (Очевидно, что в реальной реализации было бы больше методов, напримерRemoveNode(Node n)
, и т. Д.)источник
Вы могли бы даже сделать это за постоянное время O (1) (хотя это было бы не очень быстро или эффективно): существует ограниченное количество узлов, которые может хранить память вашего компьютера, скажем, N записей. Если вы пересекаете больше, чем N записей, то у вас есть цикл.
источник
источник
Используйте вышеуказанную функцию, чтобы обнаружить цикл в связанный список в Java.
источник
Обнаружение цикла в связанном списке может быть выполнено одним из самых простых способов, что приводит к сложности O (N) с использованием hashmap или O (NlogN) с использованием подхода, основанного на сортировке.
Когда вы просматриваете список, начиная с заголовка, создайте отсортированный список адресов. Когда вы вставляете новый адрес, убедитесь, что этот адрес уже есть в отсортированном списке, что требует сложности O (logN).
источник
Я не вижу никакого способа сделать так, чтобы это заняло фиксированное количество времени или пространства, и оба увеличатся с размером списка.
Я хотел бы использовать IdentityHashMap (учитывая, что IdentityHashSet еще не существует) и сохранить каждый узел на карте. Перед тем, как сохранить узел, вы должны вызвать для него containsKey. Если узел уже существует, у вас есть цикл.
ItentityHashMap использует == вместо .equals, чтобы вы проверяли, где находится объект в памяти, а не имеет ли он такое же содержимое.
источник
Я мог бы быть ужасно поздно и новичком, чтобы обращаться с этой темой. Но все равно..
Почему нельзя сохранить адрес узла и указанный «следующий» узел в таблице
Если бы мы могли составить таблицу таким образом
Отсюда и цикл.
источник
Вот мой исполняемый код.
Что я сделал, так это почитал связанный список, используя три временных узла (сложность пространства
O(1)
), которые отслеживают ссылки.Интересный факт в этом состоит в том, чтобы помочь обнаружить цикл в связанном списке, потому что по мере продвижения вперед вы не ожидаете возврата к начальной точке (корневому узлу), а один из временных узлов должен обнуляться, если только вы есть цикл, который означает, что он указывает на корневой узел.
Временная сложность этого алгоритма равна,
O(n)
а сложность пространства равнаO(1)
.Вот узел класса для связанного списка:
Вот основной код с простым тестовым примером из трех узлов, последний узел которого указывает на второй узел:
Вот простой тестовый пример трех узлов, которые последний узел указывает на второй узел:
источник
Этот код оптимизирован и даст результат быстрее, чем тот, который выбран в качестве наилучшего ответа. Этот код избавляет от необходимости очень долго пытаться отследить указатель прямого и обратного узла, что произойдет в следующем случае, если мы будем следовать «лучшим» метод ответа. Посмотрите пробную версию следующего, и вы поймете, что я пытаюсь сказать. Затем посмотрите на проблему с помощью приведенного ниже метода и измерьте число «нет». шагов, предпринятых, чтобы найти ответ.
1-> 2-> 9-> 3 ^ -------- ^
Вот код:
источник
boolean hasLoop(Node first)
который бы возвращал значение true, если данный узел является первым в списке с циклом, а в противном случае - false?Вот мое решение в Java
источник
Вы можете использовать алгоритм черепахи Флойда, как предложено в ответах выше.
Этот алгоритм может проверить, имеет ли односвязный список замкнутый цикл. Это может быть достигнуто путем итерации списка с двумя указателями, которые будут двигаться с разной скоростью. Таким образом, если есть цикл, два указателя встретятся в какой-то момент в будущем.
Пожалуйста, не стесняйтесь проверить мой блог о структуре данных связанных списков, где я также включил фрагмент кода с реализацией вышеупомянутого алгоритма на языке Java.
С Уважением,
Андреас (@xnorcode)
источник
Вот решение для обнаружения цикла.
источник
// Связанный список найти функцию цикла
источник
Этот подход требует много места, но его реализация проще:
Цикл можно определить, сохранив узлы на карте. И прежде чем ставить узел; проверьте, если узел уже существует. Если узел уже существует на карте, это означает, что связанный список имеет цикл.
источник
источник