Kaip nustatyti susieto sąrašo ciklą?

Tarkime, jūs turite susijusią sąrašo struktūrą java. Ją sudaro mazgai:

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

ir kiekvienas mazgas nukreipia į kitą mazgų, išskyrus paskutinį mazgų, kuris yra nulinis kitam. Tarkime, yra galimybė, kad sąraše gali būti ciklas, t.y. Paskutinis mazgas vietoj nulio reiškia vieną iš jo sąraše esančių mazgų.

Koks yra geriausias būdas rašyti

 boolean hasLoop(Node first) 

kuris grąžinamas true jei nurodytas mazgas yra pirmasis iš sąrašo su kilpa ir kitaip false ? Kaip galėtumėte rašyti taip, kad užtruko nuolatinę erdvę ir pagrįstą laiką?

Štai kaip atrodo kilpos sąrašas:

2019

379
18 апр. Nustatė jjujuma balandžio 18 d 2010-04-18 20:08 '10, 20:08, 2010-04-18 20:08
@ 24 atsakymai

Galite naudoti „Floyd“ ciklo paieškos algoritmą , taip pat žinomą kaip vėžlių ir tropų algoritmas.

Idėja yra turėti dvi nuorodas į sąrašą ir perkelti jas į skirtingus greičius . Perkelkite vieną priekinį 1 mazgų ir kitą mazgus 2 .

  • Jei susietas sąrašas turi ciklą, jie tikrai susitiks.
  • Dar viena iš dviejų nuorodų (arba jų next ) taps null .

„Java“ funkcija, įgyvendinanti algoritmą:

 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 апр. Atsakyti codaddict balandžio 18 2010-04-18 20:18 '10, 20:18, 2010-04-18 20:18

Jis nurodo greitą arba lėtą sprendimą, kuris teisingai apdoroja nelyginio ilgio sąrašus ir pagerina aiškumą.

 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 Atsakymą pateikė Dave L. Liepos 21, 10, 19:55 2010-07-21 19:55

Alternatyvus vėžlio ir triušio sprendimas nėra visiškai malonus, nes laikinai pakeisiu sąrašą:

Idėja yra eiti per sąrašą ir atšaukti, kai jūs einate. Tada, kai pirmą kartą pasieksite jau aplankytą mazgą, kitas rodiklis parodys „atgal“, todėl iteracija ir toliau bus vėl, kur jis baigiasi.

 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; 

Bandymo kodas:

 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 апр. atsakymas pateikiamas 20 d. 2010-04-20 04:25 '10, 4:25, 2010-04-20 04:25

Geriau nei „Floyd“ algoritmas

Richardas Brentas aprašė alternatyvų algoritmo algoritmą, kuris yra labai panašus į neapykantą ir vėžlį [Floydo ciklas], išskyrus tai, kad lėtas mazgas čia neperkelia ir tuomet „teleportuoja“ į greitą mazgų padėtį nustatytais intervalais.

Aprašymas pateikiamas čia: http://www.siafoo.net/algorithm/11 Brentas teigia, kad jo algoritmas yra 24–36% greitesnis už Floyd ciklo algoritmą. O (n), erdvės O (1) sudėtingumas.

 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 февр. atsakymą pateikė Ashok Bijoy Debnath 28 vasaris. 2013-02-28 01:24 '13 ne 1:24 2013-02-28 01:24

Vėžlys ir kiškis

Žr. „Pollard rho“ algoritmą . Tai ne visai ta pati problema, bet galbūt jūs suprasite jo logiką ir pritaikysite jį susietiems sąrašams.

(jei esate tingus, galite tiesiog patikrinti ciklo aptikimą - patikrinkite, ar dalis vėžlio ir avilio).

Tam reikalingas tik linijinis laikas ir 2 papildomi rodikliai.

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

(Dauguma sprendimų netikrina ir next ir next next.next . Be to, kadangi vėžlys visada atsilieka, jums nereikia tikrinti, ar jis yra nulis.

28
18 апр. atsakymas pateikiamas Larry 18 d. 2010-04-18 20:12 '10, 20:12, 2010-04-18 20:12

Vartotojo unicornaddict turi gerą algoritmą aukščiau, tačiau, deja, jame yra klaidų, susijusių su nelygiais nelyginio ilgio sąrašais> = 3. Problema ta, kad fast gali „įstrigti“ prieš pat sąrašo pabaigą, slow sugauti su juo ir aptikti kilpa (klaidingai ).

Čia yra patikslintas algoritmas.

 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 atsakė Carl Mäsak'ui liepos 10 d. 10:02 2010-07-01 16:02

Tai gali būti ne geriausias būdas - tai yra O (n ^ 2). Tačiau jis turi padėti atlikti darbą (galiausiai).

 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 апр. Sparky atsakymas, pateiktas balandžio 18 d 2010-04-18 20:14 '10, 20:14, 2010-04-18 20:14

Algoritmas

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

Sudėtingumas

 Time ~ O(n) Space ~ O(n) 
8
23 марта '13 в 14:14 2013-03-23 14:14 atsakymas pateikiamas Khaled.K kovo 23 d., 13 val. 14:14 2013-03-23 ​​14:14

Taip pat galite pamatyti Nivasch algoritmą : Nivash algoritmą .

Arba galite patikrinti „Gabriel Nivasch“ asmeninį puslapį, kad nustatytumėte kamino algoritmą, kad nustatytumėte kilpą , kuriame taip pat yra C algoritmo įgyvendinimas.

7
06 дек. atsakymas pateikiamas funkcionaliai 06 d. 2017-12-06 16:23 '17 16:23 PM 2017-12-06 16:23

Jei mums leidžiama įterpti Node klasę, problemą išsprendžsiu, kai ją įgyvendinau toliau. hasLoop() veikia O (n) laiku ir užima tik counter . Ar tai atrodo teisingas sprendimas? Ar galima tai padaryti be Node pridėjimo? (Akivaizdu, kad realiame įgyvendinime bus daugiau būdų, pvz., „ RemoveNode(Node n) ir tt)

 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 апр. Atsakymą pateikia smessing balandžio 21 d 2010-04-21 17:46 '10, 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; } 

Atleisk mano neišmanymą (vis dar esu visiškai naujas „Java“ ir programavimas), bet kodėl tai neveikia?

Manau, kad ji neišsprendžia problemos su pastovia erdve ... bet bent jau ten per protingą laiką, tiesa? Tai bus tik susieto sąrašo ir nustatyto ploto vieta n elementais (kur n yra susieto sąrašo elementų skaičius arba elementų skaičius, kol jis pasiekia kilpą). Ir kol kas, blogiausia analizė, manau, pasiūlytų O (nlog (n)). Rūšiuojamos užklausos yra () yra log (n) (patikrinkite javadoc, bet esu tikras, kad pagrindinė „TreeSet“ struktūra yra „TreeMap“, kuri savo ruožtu yra raudonmedžio medis), ir blogiausiu atveju (be ciklų ar kilpos gale ), jis turės atlikti n paieškas.

3
21 апр. Atsakymą pateikia smessing balandžio 21 d 2010-04-21 09:53 '10, 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 апр. Atsakymą pateikė „ Richa“ balandžio 29 d. 2016-04-29 14:13 '16 at 14:13 PM 2016-04-29 14:13

Jūs netgi galite tai padaryti pastoviu O (1) laiku (nors tai nėra labai greitas ar efektyvus): yra ribotas skaičius mazgų, kuriuos gali išsaugoti jūsų kompiuterio atmintis, pvz., N įrašai. Jei kerta daugiau nei N įrašus, tada turite kilpą.

1
15 окт. Atsakyti Eduardo Oct 15. 2012-10-15 12:51 '12 12:51 2012-10-15 12:51

Aš nematau jokio būdo tai padaryti nustatytu laiku ar erdvėje, abu padidės sąrašo dydžiu.

Norėčiau naudoti „IdentityHashMap“ (atsižvelgiant į tai, kad „IdentityHashSet“ dar nėra) ir išsaugokite kiekvieną „Node“ žemėlapyje. Prieš išsaugodami mazgas, skambinate į „Kodas“. Jei mazgas jau yra, turite kilpą.

„ItentityHashMap“ naudoja == vietoj .equals, kad patikrintumėte, kur objektas yra atmintyje, o ne to paties turinio.

0
18 апр. Atsakymas pateikiamas TofuBeer 18 d. 2010-04-18 20:22 '10, 08:22 PM 2010-04-18 20:22

Galite naudoti „Floyd“ vėžlio algoritmą, kaip aprašyta aukščiau pateiktuose atsakymuose.

Šis algoritmas gali patikrinti, ar uždara kilpa turi uždarą kilpą. Tai galima pasiekti įtraukiant sąrašą į du rodiklius, kurie judės skirtingu greičiu. Taigi, jei yra ciklas, ateityje tam tikru momentu atsiras du rodikliai.

Nedvejodami patikrinkite mano tinklaraščio įrašą apie susietų sąrašų struktūrą, kur taip pat įtraukiau kodo fragmentą su pirmiau minėto algoritmo įgyvendinimu „Java“.

Pagarbiai

Andreas (@xnorcode)

0
04 мая '18 в 1:09 2018-05-04 01:09 atsakymas pateikiamas xnorcode gegužės 4 d., 18 val. 1:09 2018-05-04 01:09

Čia yra mano vykdomasis kodas.

Tai, ką aš padariau, yra skaityti susietą sąrašą naudojant tris laikinus mazgus ( O(1) erdvės sudėtingumą), kurie seka ryšius.

Įdomus faktas apie tai yra padėti aptikti susieto sąrašo ciklą, nes kai jūs judate į priekį, nenorite grįžti į pradinį tašką (šakninis mazgas), o vienas iš laikinų mazgų turėtų būti nulinis, jei neturite kilpa, o tai reiškia, kad jis nukreipia į šaknų mazgus.

Šio algoritmo laiko sudėtingumas yra O(n) , o erdvės sudėtingumas yra O(1) .

Žemiau yra susieto sąrašo mazgo klasė:

 public class LinkedNode{ public LinkedNode next; } 

Čia yra pagrindinis kodas su paprastu trijų mazgų bandymo pavyzdžiu, kurį paskutinis mazgas nukreipia į antrąjį mazgą:

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

Toliau pateikiamas paprastas trijų mazgų pavyzdys: paskutinis mazgas, rodantis antrojo mazgo:

 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 февр. Atsakymą pateikė Habib Karbasian 10 vasaris. 2016-02-10 09:01 '16 at 9:01 am 2016-02-10 09:01

Šis kodas yra optimizuotas ir suteiks rezultatų greičiau nei pasirinktas kaip geriausias atsakymas. Šis kodas išsaugo perėjimą prie labai ilgo proceso, rodančio rodyklę į priekį ir atgal, kuris įvyks kitame atveju, jei laikysime „geriausio atsakymo“ metodo. Pažvelkite į kito sauso bėgimo kelią, ir jūs suprasite, ką bandau pasakyti. Tada pažiūrėkite į problemą naudodami toliau pateiktą metodą ir išmatuokite „ne“. imtasi veiksmų atsakymui rasti.

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

Čia yra kodas:

 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 atsakymą pateikė Sarthak Mehra, birželio 27 d., 16 val. 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; } 

Naudokite pirmiau nurodytą funkciją, jei norite rasti kilpą java susietame sąraše.

0
06 сент. atsakymą pateikė Aditya Parmar 06 sep . 2017-09-06 00:09 '17 - 0:09 2017-09-06 00:09

Susieto sąrašo kilpų aptikimas gali būti atliekamas vienu iš paprasčiausių būdų, o tai sukelia O (N) sudėtingumą.

Kai einate per sąrašą, pradedant skyriumi sukurkite suskirstytą adresų sąrašą. Įdėję naują adresą, patikrinkite, ar adresas yra surūšiuotame sąraše, kuriame yra O (logN) sudėtingumas.

0
22 июля '10 в 22:00 2010-07-22 22:00 Abhinavo atsakymas liepos 22 d. 10 val. 10:00 2010-07-22 22:00

Čia yra kilpos aptikimo sprendimas.

 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 atsakymas pateikiamas vishwaraj birželio 30 d. 18 val. 20.46. 2018-06-30 20:46

Gali būti labai vėlyvas ir naujas dalykas. Bet vis dar ..

Kodėl negalima išsaugoti mazgo adreso ir rodyklės „kito“ mazgo lentelėje

Jei galėtume pateikti tokią lentelę

 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) 

Todėl sudaromas ciklas.

0
24 янв. atsakymą pateikė Adit Ya sausio 24 d 2014-01-24 11:40 '14 at 11:40 2014-01-24 11:40

Čia yra mano sprendimas 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; } 
-1
24 сент. Atsakymas, kurį pateikė Irshad ck 24 Sep. 2017-09-24 15:50 '17 - 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 янв. atsakymas pateikiamas sausio 16 d 2013-01-16 08:05 '13, 08:05 2013-01-16 08:05

Šis požiūris turi erdvinę pridėtinę vertę, tačiau paprastesnis įgyvendinimas:

Kilpa gali būti identifikuojama saugant mazgus žemėlapyje. Ir prieš įdėdami mazgų; patikrinkite, ar yra mazgas. Jei žemėlapyje jau yra mazgas, tai reiškia, kad susietas sąrašas turi kilpą.

 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 atsakymas pateikiamas rai.skumar gegužės 09 '14, 16:08 2014-05-09 16:08