Kako definirati ciklus u povezanom popisu?

Recimo da imate povezanu strukturu popisa u javi. Sastoji se od čvorova:

 class Node { Node next; // some user data } 

i svaki čvor ukazuje na sljedeći čvor, osim posljednjeg čvora, koji je null za sljedeći. Recimo da postoji mogućnost da popis sadrži ciklus Posljednji čvor, umjesto nule, odnosi se na jedan od čvorova na popisu koji je bio ispred njega.

Koji je najbolji način pisanja

 boolean hasLoop(Node first) 

koji vraća true ako je dani Node prvi s popisa s petljom, a inače false ? Kako možete pisati tako da je trajni prostor i razumno vrijeme?

Ovako izgleda popis petlji:

2019

379
18 апр. Postavio jjujuma 18. travnja 2010-04-18 20:08 '10 u 20:08 2010-04-18 20:08
@ 24 odgovora

Možete koristiti Floydov algoritam pretraživanja , također poznat kao algoritam kornjače i zečeva.

Ideja je imati dvije veze na popis i premjestiti ih na različite brzine . Premjesti jedan čvor za naprijed 1 , a drugi na čvorove 2 .

  • Ako povezan popis ima ciklus, oni će sigurno ispuniti.
  • Još jedna od dvije veze (ili njihova next ) postat će null .

Java funkcija koja implementira algoritam:

 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; } } 
488
18 апр. Odgovori codaddict 18. tra 2010-04-18 20:18 '10 u 20:18 2010-04-18 20:18

Ona određuje brzo ili sporo rješenje koje ispravno obrađuje popise neparne duljine i poboljšava jasnoću.

border=0
 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 } 
98
21 июля '10 в 19:55 2010-07-21 19:55 Odgovor daje Dave L. 21. srpnja '10. U 19:55. 2010-07-21 19:55

Alternativno rješenje za kornjača i zec nije sasvim ugodno, jer privremeno mijenjam popis:

Ideja je proći popis i otkazati ga kada odete. Zatim, kada prvi put dođete do čvora koji je već bio posjećen, njegov sljedeći pokazivač će pokazati "natrag", s rezultatom da će se iteracija nastaviti first , gdje se završava.

 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; 

Test kod:

 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); } 
46
20 апр. odgovor je dan meriton 20 apr. 2010-04-20 04:25 '10 u 4:25 2010-04-20 04:25

Bolje od Floydova algoritma

Richard Brent je opisao alternativni algoritam algoritma koji je vrlo sličan zecu i kornjači [Floydov ciklus], osim što se spor čvor ne pomiče ovdje i zatim "teleportira" u poziciju brzog čvora u fiksnim intervalima.

Opis dostupan ovdje: http://www.siafoo.net/algorithm/11 Brent tvrdi da je njegov algoritam 24–36% brži od algoritma Floydovog ciklusa. O (n), složenost prostora 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 position) } } return false; } 
44
28 февр. odgovor daje Ashok Bijoy Debnath 28. veljače. 2013-02-28 01:24 '13 u 1:24 2013-02-28 01:24

Kornjača i zec

Vidi Pollardov rho algoritam . To nije posve isti problem, ali možda ćete razumjeti njegovu logiku i primijeniti ga na povezane popise.

(ako ste lijeni, možete samo provjeriti otkrivanje ciklusa - provjerite dio kornjače i zeca.)

To zahtijeva samo linearno vrijeme i 2 dodatna pokazivača.

U Javi:

 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; } 

(Većina rješenja ne provjerava za next i next.next za nule. Osim toga, budući da je kornjača uvijek iza, ne morate je provjeravati za nulu - zec je to već učinio.)

28
18 апр. odgovor je dao Larry 18. travnja. 2010-04-18 20:12 '10 u 20:12 2010-04-18 20:12

Korisnik unicornaddict ima dobar algoritam gore, ali nažalost sadrži pogrešku za ne-loop liste neparne duljine> = 3. Problem je u tome što se fast može "zaglaviti" neposredno prije kraja popisa, slow uhvatiti i detektira se petlja (pogrešno) ).

Ovdje je podešen algoritam.

 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; } } 
13
01 июля '10 в 16:02 2010-07-01 16:02 odgovorio je Carlu Mäsaku na 1. srpnja '10 u 16:02 2010-07-01 16:02

Sljedeće možda nije najbolja metoda - to je O (n ^ 2). Međutim, ona mora služiti za obavljanje posla (u konačnici).

 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++; } 
8
18 апр. Odgovor dao Sparky 18. travnja 2010-04-18 20:14 '10 u 20:14 2010-04-18 20:14

Algoritam

 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; } 

složenost

 Time ~ O(n) Space ~ O(n) 
8
23 марта '13 в 14:14 2013-03-23 14:14 odgovor je dat Khaled.K 23. ožujka '13 u 14:14 2013-03-23 ​​14:14

Također možete vidjeti Nivasch algoritam : Nivash algoritam .

Ili možete provjeriti osobnu stranicu Gabriel Nivasch za algoritam stog za određivanje petlje , koja također sadrži implementaciju algoritma C.

7
06 дек. odgovor je dat funkcionalno 06 dec. 2017-12-06 16:23 '17 at 4:23 2017-12-06 16:23

Ako nam je dopušteno umetnuti Node klasu, riješio bih problem dok sam ga implementirao ispod. hasLoop() radi u vremenu O (n) i zauzima samo prostor counter . Čini li se to kao pravo rješenje? Ili postoji način da to učinite bez privitka Node ? (Očito, u stvarnoj implementaciji bilo bi više metoda kao što je RemoveNode(Node n) , itd.)

 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; .... } } 
3
21 апр. Odgovor se daje smessing 21. travnja 2010-04-21 17:46 '10 u 17:46 2010-04-21 17:46
 public boolean hasLoop(Node start){ TreeSet<Node> set = new TreeSet<Node>(); Node lookingAt = start; while (lookingAt.peek() != null){ lookingAt = lookingAt.next; if (set.contains(lookingAt){ return false; } else { set.put(lookingAt); } return true; } // Inside our Node class: public Node peek(){ return this.next; } 

Oprostite mi na neznanju (još sam posve nov u Java i programiranju), ali zašto to ne radi?

Pretpostavljam da to ne rješava problem stalnim prostorom ... ali barem tamo stiže u razumnom roku, zar ne? To će zauzeti samo mjesto povezanog popisa plus postavljeni prostor s n elemenata (gdje je n broj elemenata u povezanom popisu ili broj elemenata dok ne dosegne petlju). I neko vrijeme, najgora analiza, mislim, sugerira O (nlog (n)). Sortirani upiti za contains () su log (n) (provjerite javadoc, ali siguran sam da je osnovna struktura TreeSapa TreeMap, koji je pak crveno-ebony stablo), au najgorem slučaju (bez ciklusa ili petlje na samom kraju) ), morat će obaviti n pretraživanja.

3
21 апр. Odgovor se daje smessing 21. travnja 2010-04-21 09:53 '10 u 9:53 2010-04-21 09:53
  // 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 next // pointer is ever equal to slower then it a circular list else if (slower == faster || slower == faster.next) return true; else { // advance the pointers slower = slower.next; faster = faster.next.next; } } } 
1
29 апр. Odgovor je dao Richa 29. travnja. 2016-04-29 14:13 '16 u 14:13 2016-04-29 14:13

To možete učiniti čak iu konstantnom vremenu O (1) (iako to ne bi bilo jako brzo ili učinkovito): postoji ograničen broj čvorova koje memorija vašeg računala može pohraniti, na primjer N zapisa. Ako prijeđete više od N zapisa, tada imate petlju.

1
15 окт. Odgovori Eduardo 15. listopada. 2012-10-15 12:51 '12 u 12:51 2012-10-15 12:51

Ne vidim način da to učinite u određenom vremenu ili prostoru, oboje će se povećati s veličinom popisa.

Ja bih koristiti IdentityHashMap (s obzirom da IdentityHashSet još ne postoji) i spremiti svaki Node na karti. Prije nego što spremite Čvor, na njemu ćete pozvati sadržiKey. Ako čvor već postoji, imate petlju.

ItentityHashMap koristi == umjesto .equals tako da provjerite gdje je objekt u memoriji, a ne u istom sadržaju.

0
18 апр. Odgovor je dat TofuBeer 18. travnja. 2010-04-18 20:22 '10 u 20:22 2010-04-18 20:22

Možete koristiti algoritam Floyd kornjača kao što je opisano u gornjim odgovorima.

Ovaj algoritam može provjeriti ima li zatvorena petlja zatvorenu petlju. To se može postići ponavljanjem popisa s dva pokazivača koji će se kretati različitim brzinama. Dakle, ako postoji ciklus, dvije točke će se pojaviti u nekom trenutku u budućnosti.

Slobodno provjerite moj blog post o strukturi povezanih popisa, gdje sam također uključio isječak koda s implementacijom gore navedenog algoritma u Javi.

S poštovanjem,

Andreas (@xnorcode)

0
04 мая '18 в 1:09 2018-05-04 01:09 odgovor je dan xnorcode 4. svibnja '18 u 1:09 2018-05-04 01:09

Ovdje je moj izvršni kôd.

Ono što sam učinio jest da pročitam povezani popis koristeći tri privremena čvora ( O(1) prostorna složenost) koji prate veze.

Zanimljiva činjenica o tome je da pomogne u otkrivanju ciklusa u povezanom popisu, jer kada se krećete naprijed, ne očekujete povratak na početnu točku (korijenski čvor), a jedan od privremenih čvorova treba ići na null ako nemate petlje, što znači da pokazuje na korijenski čvor.

Vremenska složenost ovog algoritma je O(n) , a složenost prostora je O(1) .

Dolje je klasa čvora za povezani popis:

 public class LinkedNode{ public LinkedNode next; } 

Ovdje je glavni kod s jednostavnim testnim primjerom od tri čvora, koji posljednji čvor pokazuje na drugi čvor:

  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; } 

Slijedi jednostavan primjer triju čvorova: posljednji čvor koji upućuje na drugi čvor:

 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)); } } 
0
10 февр. Odgovor daje Habib Karbasian 10. veljače. 2016-02-10 09:01 '16 u 9:01 am 2016-02-10 09:01

Ovaj kod je optimiziran i rezultirat će bržim rezultatima od onih odabranih kao najbolji odgovor. Ovaj kod štedi od prijelaza na vrlo dug proces u potrazi za pokazivačem natrag i naprijed čvora, koji će se pojaviti u sljedećem slučaju, ako slijedimo metodu "najboljeg odgovora". Pogledajte suhu vožnju sljedećeg i shvatit ćete što pokušavam reći. Zatim pogledajte problem pomoću donje metode i izmjerite "ne". poduzeti korake kako bi pronašli odgovor.

1-> 2-> 9-> 3 ^ -------- ^

Evo koda:

 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 } 
0
27 июня '16 в 23:03 2016-06-27 23:03 odgovor je dao Sarthak Mehra 27. lipnja 2006. u 23:03 2016-06-27 23:03
 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; } 

Koristite gornju funkciju da biste pronašli petlju u popisu povezanog s java.

0
06 сент. odgovor daje Aditya Parmar 06 sep . 2017-09-06 00:09 '17 u 0:09 2017-09-06 00:09

Detekcija petlje u povezanom popisu može se izvesti na jedan od najjednostavnijih načina, što rezultira složenošću O (N).

Dok pregledavate popis, počevši s poglavljem, napravite sortiranu listu adresa. Kada umetnete novu adresu, provjerite je li adresa u razvrstanoj listi koja čini O (logN) složenost.

0
22 июля '10 в 22:00 2010-07-22 22:00 Odgovor dao Abhinav 22. srpnja 2010. u 10:00 2010-07-22 22:00

Ovdje je rješenje za detekciju petlje.

 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 } 
0
30 июня '18 в 20:46 2018-06-30 20:46 odgovor je dat vishwaraj 30. lipnja '18 u 20:46 sati 2018-06-30 20:46

Možda sam vrlo kasno i nov u ovoj temi. Ali još uvijek ..

Zašto ne možete spremiti adresu čvora i pokazivač "sljedeći" čvor u tablici

Ako bismo mogli tabelirati na ovaj način

 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) 

Stoga se formira ciklus.

0
24 янв. odgovor je dao Adit Ya 24. siječnja 2014-01-24 11:40 '14 u 11:40 2014-01-24 11:40

Ovo je moje rješenje u javi

 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; } 
-1
24 сент. Odgovor dao Irshad ck 24. rujna. 2017-09-24 15:50 '17 u 15:50 2017-09-24 15:50
 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; } 
-1
16 янв. odgovor je dan 16. siječnja 2013-01-16 08:05 '13 u 8:05 2013-01-16 08:05

Ovaj pristup ima prostorno opterećenje, ali jednostavniju implementaciju:

Petlja se može identificirati pohranjivanjem čvorova na karti. I prije nego što stavite čvor; provjerite postoji li čvor. Ako čvor već postoji na karti, to znači da Linked List ima petlju.

 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; } 
-1
09 мая '14 в 16:08 2014-05-09 16:08 odgovor je dan rai.skumar Svibanj 09 '14 u 16:08 2014-05-09 16:08