Запомните это:
Потребители едят ужин (супер); Производитель продлевает фабрику своего родителя
blockquote>
Вы можете использовать алгоритм поиска циклов Флойда , также известный как алгоритм черепахи и зайца . Идея состоит в том, чтобы иметь две ссылки на список и перемещать их с разной скоростью. Переместите один вперед узлом 1
, а другой - узлами 2
.
next
) будет [f6] Функция Java, реализующая алгоритм:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}
Возможно, я очень устал и новичок в этой теме. Но все же ..
Почему не может быть указан адрес узла, а указатель «следующий» указывается в таблице
. Если мы могли бы табулировать этот путь
node present: (present node addr) (next node address)
node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)
Следовательно, образуется цикл.
boolean hasCycle(Node head) {
boolean dec = false;
Node first = head;
Node sec = head;
while(first != null && sec != null)
{
first = first.next;
sec = sec.next.next;
if(first == sec )
{
dec = true;
break;
}
}
return dec;
}
Используйте функцию выше, чтобы обнаружить цикл в связанном списке в java.
Лучше, чем алгоритм Флойда
Ричард Брент описал алгоритм обнаружения альтернативного цикла , который в значительной степени похож на зайца и черепаху [цикл Флойда ], за исключением того, что медленный узел здесь не перемещается, а затем «телепортируется» в положение быстрого узла с фиксированными интервалами.
Описание доступно здесь: http://www.siafoo.net/algorithm/11 Брент утверждает, что его алгоритм на 24-36% быстрее, чем алгоритм цикла Флойда. O (n), сложность пространства O (1).
public static boolean hasLoop(Node root){
if(root == null) return false;
Node slow = root, fast = root;
int taken = 0, limit = 2;
while (fast.next != null) {
fast = fast.next;
taken++;
if(slow == fast) return true;
if(taken == limit){
taken = 0;
limit <<= 1; // equivalent to limit *= 2;
slow = fast; // teleporting the turtle (to the hare's position)
}
}
return false;
}
slow.next != null
? Насколько я вижу, slow
всегда позади или равен fast
.
– TWiStErRob
19 November 2015 в 10:38
Пользователь unicornaddict имеет хороший алгоритм выше, но, к сожалению, он содержит ошибку для нециклических списков нечетной длины> = 3. Проблема в том, что fast
может «застрять» просто до конца списка, slow
догоняет его, и обнаружен цикл (ошибочно).
Вот исправленный алгоритм.
static boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next == null)
fast = null;
else
fast = fast.next.next; // 2 hops.
if(fast == null) // if fast hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
Вот уточнение решения Fast / Slow, которое правильно обрабатывает списки нечетных длин и улучшает четкость.
boolean hasLoop(Node first) {
Node slow = first;
Node fast = first;
while(fast != null && fast.next != null) {
slow = slow.next; // 1 hop
fast = fast.next.next; // 2 hops
if(slow == fast) // fast caught up to slow, so there is a loop
return true;
}
return false; // fast reached null, so the list terminates
}
slow == fast.next
, то slow
будет равно fast
на самой следующей итерации; он экономит только одну итерацию максимум за счет дополнительного теста для каждой итерации.
– Jason C
6 March 2014 в 01:59
slow
не может стать нулевым до fast
, поскольку он соответствует одному и тому же пути ссылок (если у вас нет одновременной модификации списка, в этом случае все ставки отключены).
– Dave L.
15 October 2014 в 15:57
public boolean isCircular() {
if (head == null)
return false;
Node temp1 = head;
Node temp2 = head;
try {
while (temp2.next != null) {
temp2 = temp2.next.next.next;
temp1 = temp1.next;
if (temp1 == temp2 || temp1 == temp2.next)
return true;
}
} catch (NullPointerException ex) {
return false;
}
return false;
}
Вы могли бы даже сделать это в постоянное время O (1) (хотя это было бы не очень быстро или эффективно): существует ограниченное количество узлов, хранящихся в памяти вашего компьютера, например N записей. Если вы пересекаете более N записей, тогда у вас есть цикл.
Вот мой исполняемый код.
Я сделал это, чтобы почитать связанный список, используя три временных узла (сложность пространства O(1)
), которые отслеживают ссылки.
Интересный факт заключается в том, чтобы помочь обнаружить цикл в связанном списке, потому что, когда вы продвигаетесь вперед, вы не ожидаете вернуться к начальной точке (корневому узлу) и одному из временных узлы должны идти до нуля, если у вас нет цикла, что означает, что он указывает на корневой узел.
Временная сложность этого алгоритма - O(n)
, а сложность пространства - O(1)
.
Вот узел класса для связанного списка:
public class LinkedNode{
public LinkedNode next;
}
Вот основной код с простым тестовым случаем из трех узлов, который последний узел указывает на второй узел:
public static boolean checkLoopInLinkedList(LinkedNode root){
if (root == null || root.next == null) return false;
LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
root.next = null;
current2.next = current1;
while(current3 != null){
if(current3 == root) return true;
current1 = current2;
current2 = current3;
current3 = current3.next;
current2.next = current1;
}
return false;
}
Вот простой тестовый пример из трех узлов, который указывает последний узел ко второму узлу:
public class questions{
public static void main(String [] args){
LinkedNode n1 = new LinkedNode();
LinkedNode n2 = new LinkedNode();
LinkedNode n3 = new LinkedNode();
n1.next = n2;
n2.next = n3;
n3.next = n2;
System.out.print(checkLoopInLinkedList(n1));
}
}
Вот мое решение в java
boolean detectLoop(Node head){
Node fastRunner = head;
Node slowRunner = head;
while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if(fastRunner == slowRunner){
return true;
}
}
return false;
}
Обнаружение цикла в связанном списке может быть выполнено одним из самых простых способов, что приводит к сложности O (N).
По мере прохождения списка, начиная с главы, создайте отсортированный список адреса. Когда вы вставляете новый адрес, проверьте, есть ли адрес в отсортированном списке, который выполняет сложность O (logN).
Алгоритм
public static boolean hasCycle (LinkedList<Node> list)
{
HashSet<Node> visited = new HashSet<Node>();
for (Node n : list)
{
visited.add(n);
if (visited.contains(n.next))
{
return true;
}
}
return false;
}
Сложность
Time ~ O(n)
Space ~ O(n)
equals
и hashCode
. Это не одно и то же. И это разметки null
на последнем элементе. И вопрос ничего не сказал о хранении узлов в LinkedList
.
– Lii
17 August 2015 в 18:35
Альтернативное решение для Черепахи и Кролика, не совсем так приятно, поскольку я временно меняю список:
Идея состоит в том, чтобы ходить по списку и отменить его, когда вы идете. Затем, когда вы впервые достигнете узла, который уже был посещен, его следующий указатель будет указывать «назад», в результате чего итерация снова начнется к first
, где она завершается.
Node prev = null;
Node cur = first;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;
// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return hasCycle;
Тестовый код :
static void assertSameOrder(Node[] nodes) {
for (int i = 0; i < nodes.length - 1; i++) {
assert nodes[i].next == nodes[i + 1];
}
}
public static void main(String[] args) {
Node[] nodes = new Node[100];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node();
}
for (int i = 0; i < nodes.length - 1; i++) {
nodes[i].next = nodes[i + 1];
}
Node first = nodes[0];
Node max = nodes[nodes.length - 1];
max.next = null;
assert !hasCycle(first);
assertSameOrder(nodes);
max.next = first;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = max;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = nodes[50];
assert hasCycle(first);
assertSameOrder(nodes);
}
Взгляните на алгоритм Роллара Полларда . Это не совсем та же проблема, но, может быть, вы поймете ее логику и примените ее к связанным спискам.
(если вы ленивы, вы можете просто проверить обнаружение цикла - проверьте часть черепахи и зайца.)
Для этого требуется только линейное время и 2 дополнительных указателя.
В Java:
boolean hasLoop( Node first ) {
if ( first == null ) return false;
Node turtle = first;
Node hare = first;
while ( hare.next != null && hare.next.next != null ) {
turtle = turtle.next;
hare = hare.next.next;
if ( turtle == hare ) return true;
}
return false;
}
(Большинство решений не проверяют как для next
, так и для next.next
для нулей. Кроме того, поскольку черепаха всегда отстает, вам не нужно проверять ее на нуль - заяц сделал это уже. )
Этот подход имеет пространственные накладные расходы, но более простая реализация:
Петля может быть идентифицирована путем хранения узлов на карте. И прежде чем положить узел; проверьте, существует ли узел. Если узел уже существует на карте, это означает, что Linked List имеет цикл.
public boolean loopDetector(Node<E> first) {
Node<E> t = first;
Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();
while (t != null) {
if (map.containsKey(t)) {
System.out.println(" duplicate Node is --" + t
+ " having value :" + t.data);
return true;
} else {
map.put(t, t);
}
t = t.next;
}
return false;
}
// To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
Node slower, faster;
slower = head;
faster = head.next; // start faster one node ahead
while (true) {
// if the faster pointer encounters a NULL element
if (faster == null || faster.next == null)
return false;
// if faster pointer ever equals slower or faster's next
// pointer is ever equal to slower then it's a circular list
else if (slower == faster || slower == faster.next)
return true;
else {
// advance the pointers
slower = slower.next;
faster = faster.next.next;
}
}
}
Этот код оптимизирован и приведет к результату быстрее, чем к выбранному в качестве наилучшего ответа. Этот код экономит от перехода на очень длительный процесс преследования указателя на передний и задний узлы, который будет происходить в следующем случае, если мы последуем метод «лучшего ответа». Посмотрите на сухой пробег следующего, и вы поймете, что я пытаюсь сказать. Затем посмотрите на проблему с помощью приведенного ниже метода и измерьте «нет». шагов, предпринятых для поиска ответа.
1-> 2-> 9-> 3 ^ -------- ^
Вот код:
boolean loop(node *head)
{
node *back=head;
node *front=head;
while(front && front->next)
{
front=front->next->next;
if(back==front)
return true;
else
back=back->next;
}
return false
}
boolean hasLoop(Node first)
, который вернет true, если данный узел является первым из списка с циклом, а false в противном случае?
– Sunreef
28 June 2016 в 13:10
Если нам разрешено вставлять класс Node
, я бы решил проблему, как я ее реализовал ниже. hasLoop()
работает в O (n) времени и занимает только пространство counter
. Кажется ли это подходящим решением? Или есть способ сделать это без вложения Node
? (Очевидно, что в реальной реализации было бы больше методов, таких как RemoveNode(Node n)
и т. Д.)
public class LinkedNodeList {
Node first;
Int count;
LinkedNodeList(){
first = null;
count = 0;
}
LinkedNodeList(Node n){
if (n.next != null){
throw new error("must start with single node!");
} else {
first = n;
count = 1;
}
}
public void addNode(Node n){
Node lookingAt = first;
while(lookingAt.next != null){
lookingAt = lookingAt.next;
}
lookingAt.next = n;
count++;
}
public boolean hasLoop(){
int counter = 0;
Node lookingAt = first;
while(lookingAt.next != null){
counter++;
if (count < counter){
return false;
} else {
lookingAt = lookingAt.next;
}
}
return true;
}
private class Node{
Node next;
....
}
}
Следующим может быть не лучший метод - это O (n ^ 2). Тем не менее, это должно служить для выполнения работы (в конечном итоге).
count_of_elements_so_far = 0;
for (each element in linked list)
{
search for current element in first <count_of_elements_so_far>
if found, then you have a loop
else,count_of_elements_so_far++;
}
Я не вижу никакого способа сделать это фиксированным количеством времени или пространства, оба будут увеличиваться с размером списка.
Я бы использовал IdentityHashMap (учитывая, что нет но IdentityHashSet) и хранить каждый узел в карте. Прежде чем узел будет сохранен, вы вызовете containsKey на нем. Если узел уже существует, у вас есть цикл.
ItentityHashMap использует == вместо .equals, чтобы вы проверяли, где находится объект в памяти, а не в том же содержимом.
Вот решение для определения цикла.
public boolean hasCycle(ListNode head) {
ListNode slow =head;
ListNode fast =head;
while(fast!=null && fast.next!=null){
slow = slow.next; // slow pointer only one hop
fast = fast.next.next; // fast pointer two hops
if(slow == fast) return true; // retrun true if fast meet slow pointer
}
return false; // return false if fast pointer stop at end
}
Вы можете использовать алгоритм черепахи Флойда, как это предложено в вышеприведенных ответах.
Этот алгоритм может проверить, имеет ли одиночный список замкнутый цикл. Это может быть достигнуто путем итерации списка двумя указателями, которые будут двигаться с разной скоростью. Таким образом, если есть цикл, два указателя будут встречаться в какой-то момент в будущем.
Пожалуйста, не стесняйтесь проверить мой блог в блоге в структуре данных связанных списков , где я также включил фрагмент кода с реализацией вышеупомянутого алгоритма в Java-языке.
С уважением,
Andreas (@xnorcode)
fast.next
, прежде чем снова вызватьnext
:if(fast.next!=null)fast=fast.next.next;
– cmptrgeekken 18 April 2010 в 18:27