Jak wykryć pętlę na połączonej liście?

434

Załóżmy, że masz połączoną strukturę listy w Javie. Składa się z węzłów:

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

i każdy Węzeł wskazuje na następny węzeł, z wyjątkiem ostatniego Węzła, który ma wartość null dla następnego. Powiedzmy, że istnieje możliwość, że lista może zawierać pętlę - tj. Końcowy Węzeł, zamiast mieć wartość NULL, ma odniesienie do jednego z węzłów na liście, który był przed nim.

Jaki jest najlepszy sposób pisania

boolean hasLoop(Node first)

co by zwróciło, truegdyby dany Węzeł był pierwszym z listy z pętlą, a w falseprzeciwnym razie? Jak mogłeś pisać, aby zajmowała stałą ilość miejsca i rozsądną ilość czasu?

Oto zdjęcie, jak wygląda lista z pętlą:

alternatywny tekst

jjujuma
źródło
50
Wow .. Bardzo chciałbym pracować dla tego pracodawcy finite amount of space and a reasonable amount of time?:)
codaddict
10
@SLaks - pętla nie musi zapętlać z powrotem do pierwszego węzła. Może powrócić do połowy.
jjujuma
109
Poniższe odpowiedzi są warte przeczytania, ale takie pytania podczas wywiadu są okropne. Albo znasz odpowiedź (tzn. Widziałeś wariant algorytmu Floyda), albo nie, i nie robi nic, by sprawdzić swoje rozumowanie lub zdolność projektowania.
GaryF
3
Szczerze mówiąc, większość „algorytmów wiedzy” jest taka - chyba że robisz rzeczy na poziomie badawczym!
Larry
12
@GaryF A jednak odkrycie, co zrobiliby, gdyby nie znali odpowiedzi, byłoby odkrywcze. Np. Jakie kroki by podjęli, z kim mieliby pracować, co zrobiliby, aby przezwyciężyć brak wiedzy o algorytmach?
Chris Knight

Odpowiedzi:

538

Możesz skorzystać z algorytmu Floyda znajdującego cykl , znanego również jako algorytm żółwia i zająca .

Chodzi o to, aby mieć dwa odniesienia do listy i przenosić je z różnymi prędkościami . Przesuwaj jeden do przodu o 1węzeł, a drugi o 2węzły.

  • Jeśli lista połączona ma pętlę, na pewno się spotkają.
  • W przeciwnym razie stanie się jedno z dwóch odniesień (lub ich next) null.

Funkcja Java implementująca algorytm:

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;
    }
}
kodaddict
źródło
29
fast.nextPrzed nextponownym dzwonieniem należy również wykonać kontrolę zerową :if(fast.next!=null)fast=fast.next.next;
cmptrgeekken,
12
powinieneś sprawdzić nie tylko (wolno == szybko), ale: (wolno == szybko || wolno.next == szybko), aby zapobiec przeskakiwaniu postu przez wolne
Oleg Razgulyaev
13
myliłem się: szybko nie można przeskakiwać wolno, ponieważ przeskakiwanie przez wolne tempo w następnym kroku powinno mieć taką samą pozycję jak powolne :)
Oleg Razgulyaev
4
Sprawdzanie wartości slow == null jest zbędne, chyba że lista ma tylko jeden węzeł. Możesz także pozbyć się jednego połączenia z Node.next. Oto prostsza i szybsza wersja pętli: pastie.org/927591
Kay Sarraute
22
Powinieneś naprawdę zacytować swoje referencje. Algorytm ten został wynaleziony przez Roberta Floyda w latach 60., znany jako algorytm Floyda do wyszukiwania cykli, znany również jako. Algorytm żółwia i zająca.
joshperry
127

Oto udoskonalenie rozwiązania Fast / Slow, które poprawnie obsługuje listy nieparzystych długości i poprawia przejrzystość.

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
}
Dave L.
źródło
2
Miły i zwięzły. Ten kod można zoptymalizować, sprawdzając, czy wolno == szybko || (fast.next! = null && slow = fast.next); :)
arachnode.net
11
@ arachnode.net To nie jest optymalizacja. Jeśli slow == fast.nextto slowbędzie równe fastprzy następnej iteracji; oszczędza tylko jedną iterację najwyżej kosztem dodatkowego testu dla każdej iteracji.
Jason C
@ ana01 slownie może stać się wcześniej zerowy, fastponieważ podąża tą samą ścieżką referencji (chyba że masz jednoczesną modyfikację listy, w którym to przypadku wszystkie zakłady są wyłączone).
Dave L.
Z ciekawości, jak to działa w przypadku liczb nieparzystych? Czy zając nadal nie może pokonać żółwia na niepowiązanych listach?
theGreenCabbage,
1
@theGreenCabbage Z każdą iteracją pętli zając przechodzi o 1 krok dalej przed żółwiem. Więc jeśli zając jest w tyle o 3 kroki, to następna iteracja zajmuje dwa przeskoki, a żółw ma jeden skok, a teraz zając jest w tyle o 2 kroki. Po następnej iteracji zając wyprzedza o 1 skok, a następnie jest dokładnie dogoniony. Jeśli zając zajął 3 przeskoki, podczas gdy żółw wziął jeden, wówczas mógłby przejść obok, ponieważ zyskałby o 2 za każdym razem, ale ponieważ zyskuje tylko o 1 za każdym razem, nie może pominąć.
Dave L.
52

Lepszy niż algorytm Floyda

Richard Brent opisał alternatywny algorytm wykrywania cyklu , który jest podobny do zająca i żółwia [cykl Floyda], z wyjątkiem tego, że wolny węzeł tutaj się nie porusza, ale jest później „teleportowany” do pozycji szybkiego węzła na stałym poziomie interwały.

Opis jest dostępny tutaj: http://www.siafoo.net/algorithm/11 Brent twierdzi, że jego algorytm jest 24 do 36% szybszy niż algorytm cyklu Floyda. O (n) złożoność czasu, O (1) złożoność przestrzeni.

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;
}
Ashok Bijoy Debnath
źródło
Ta odpowiedź jest niesamowita!
valin077
1
Naprawdę podobała mi się twoja odpowiedź, umieściłem ją na moim blogu - k2code.blogspot.in/2010/04/… .
kinshuk4
Dlaczego musisz to sprawdzić slow.next != null? O ile widzę slowjest zawsze z tyłu lub równa fast.
TWiStErRob
Zrobiłem to dawno temu, kiedy zacząłem uczyć się algorytmów. Edytowałem kod. Dzięki :)
Ashok Bijoy Debnath
50

Alternatywne rozwiązanie dla Żółwia i Królika, niezbyt miłe, ponieważ tymczasowo zmieniam listę:

Chodzi o to, aby przejrzeć listę i odwrócić ją w trakcie podróży. Następnie, gdy pierwszy raz dotrzesz do węzła, który już był odwiedzany, jego następny wskaźnik będzie wskazywał „do tyłu”, powodując, że iteracja zacznie się firstponownie w kierunku , w którym się kończy.

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;

Kod testowy:

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);
}
meriton
źródło
Czy odwrotność działa poprawnie, gdy pętla wskazuje inny węzeł niż pierwszy? Jeśli początkowa lista połączona wygląda tak: 1-> 2-> 3-> 4-> 5-> 2 (z cyklem od 5 do 2), to odwrócona lista wygląda jak 1-> 2 <-3 <-4 <-5? A jeśli jest na odwrót, ostateczna zrekonstruowana lista zostanie spieprzona?
Zenil,
1
@Zenil: Dlatego napisałem ostatnią walizkę testową, w której ostatni węzeł wskazuje środek listy. Jeśli rekonstrukcja nie zadziała, test się nie powiedzie. O twoim przykładzie: odwrócenie 1-> 2-> 3-> 5-> 2 byłoby 1-> 2-> 5-> 4-> 3-> 2, ponieważ pętla zatrzymuje się tylko raz na końcu listy został osiągnięty, a nie po osiągnięciu końca pętli (którego nie możemy łatwo wykryć).
meriton
28

Żółw i zając

Spójrz na algorytm rho Pollarda . Nie jest to ten sam problem, ale być może zrozumiesz logikę z niego i zastosujesz go do list połączonych.

(jeśli jesteś leniwy, możesz po prostu sprawdzić wykrywanie cyklu - sprawdź część dotyczącą żółwia i zająca).

Wymaga to tylko czasu liniowego i 2 dodatkowych wskaźników.

W Javie:

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

(Większość rozwiązań nie sprawdza zarówno dla zer, jak nexti next.nextdla zer. Ponadto, ponieważ żółw jest zawsze z tyłu, nie musisz go sprawdzać pod kątem zerowości - zając już to zrobił.)

Larry
źródło
13

Unicornaddict użytkownika ma fajny algorytm powyżej, ale niestety zawiera błąd w listach niepętlowych o nieparzystej długości> = 3. Problem polega na tym, że fastmoże utknąć tuż przed końcem listy, slowłapie go i pętla jest (błędnie) wykrywana.

Oto poprawiony algorytm.

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;
    }
}
Carl Mäsak
źródło
10

W tym kontekście wszędzie jest mnóstwo materiałów tekstowych. Chciałem tylko zamieścić schematyczną reprezentację, która naprawdę pomogła mi zrozumieć tę koncepcję.

Kiedy szybkie i wolne spotykają się w punkcie p,

Przebyta odległość = a + b + c + b = a + 2b + c

Przebyty powolny dystans = a + b

Ponieważ szybki jest 2 razy szybszy niż wolny. Więc a + 2b + c = 2 (a + b) , a następnie otrzymujemy a = c .

Tak więc, gdy kolejny wolny wskaźnik ponownie uruchomi się od głowy do q , jednocześnie szybki wskaźnik będzie przebiegał od p do q , więc spotykają się w punkcie q razem.

wprowadź opis zdjęcia tutaj

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}
Neil
źródło
2
Zdjęcie jest warte więcej niż tysiące słów. Dzięki za miłe i proste wyjaśnienie!
Calios
1
Najlepsze wyjaśnienie w Internecie. Chciałbym tylko dodać, że dowodzi to, że szybki i wolny wskaźnik zbiegają się po czasie liniowym
VarunPandey,
jeśli ajest większa niż długość pętli, wówczas szybkie utworzy wiele pętli, a formuła distance (fast) = a + b + b + czmieni się na a + (b+c) * k + bwprowadzenie dodatkowego parametru, kktóry zlicza liczbę lopps wykonanych przez szybki.
Ben
9

Algorytm

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

Złożoność

Time ~ O(n)
Space ~ O(n)
Khaled.K
źródło
Jaka jest złożoność przestrzeni O (2n)?
Programator345
@ user3543449 masz rację, powinno być po prostu nnaprawione
Khaled.K 20.04.15
1
W rzeczywistości jest to czas ~ O (n ^ 2), ponieważ każda zawiera sprawdzanie, czy ArrayList przyjmuje O (n) i jest O (n) z nich. Zamiast tego użyj HashSet dla czasu liniowego.
Dave L.
3
To nie sprawdza cykli, ale duplikuje wartości przy użyciu elementów equalsi hashCode. To nie to samo. I to wyklucza nullostatni element. Pytanie nie mówiło nic o przechowywaniu węzłów w LinkedList.
Lii,
2
@Lii to pseudo-kod, to nie jest kod Java, dlatego
nazwałem
8

Poniższa metoda może nie być najlepszą metodą - jest to O (n ^ 2). Powinno to jednak służyć do wykonania zadania (ostatecznie).

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++;
}
iskrzący
źródło
Skąd miałbyś wiedzieć, ile elementów jest na liście, aby wykonać for ()?
Jethro Larson
@JethroLarson: Ostatni węzeł na połączonej liście wskazuje znany adres (w wielu implementacjach jest to NULL). Zakończ pętlę for, gdy ten znany adres zostanie osiągnięty.
Sparky
3
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;
}

Wybacz mi moją ignorancję (wciąż jestem całkiem nowy w Javie i programowaniu), ale dlaczego powyższe nie zadziałałoby?

Myślę, że to nie rozwiązuje stałego problemu z przestrzenią ... ale przynajmniej dotrze tam w rozsądnym czasie, prawda? Zajmie tylko przestrzeń połączonej listy plus przestrzeń zestawu z n elementami (gdzie n jest liczbą elementów na połączonej liście lub liczbą elementów, dopóki nie osiągnie pętli). I na razie, moim zdaniem, analiza najgorszego przypadku sugerowałaby O (nlog (n)). Wyszukiwania SortedSet dla zawiera () są log (n) (sprawdź javadoc, ale jestem pewien, że podstawową strukturą TreeSet jest TreeMap, którego z kolei jest czerwono-czarne drzewo), aw najgorszym przypadku (bez pętli, lub zapętlić na samym końcu), będzie musiał wykonać n przeglądów.

smessing
źródło
2
Tak, rozwiązanie z pewnego rodzaju zestawem działa dobrze, ale wymaga miejsca proporcjonalnego do wielkości listy.
jjujuma
3

Jeśli pozwolimy osadzić klasę Node, rozwiązałbym problem, ponieważ zaimplementowałem go poniżej. hasLoop()działa w czasie O (n) i zajmuje tylko przestrzeń counter. Czy to wydaje się odpowiednie rozwiązanie? A może jest to zrobić bez osadzania Node? (Oczywiście w prawdziwej implementacji byłoby więcej metod, takich jak RemoveNode(Node n)itp.)

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

}
smessing
źródło
1

Możesz to zrobić nawet w stałym czasie O (1) (choć nie byłoby to zbyt szybkie ani wydajne): istnieje ograniczona liczba węzłów w pamięci komputera, na przykład N rekordów. Jeśli przejdziesz więcej niż N rekordów, masz pętlę.

Eduardo
źródło
To nie jest O (1), ten algorytm nie ma znaczącej złożoności czasowej w notacji big-O. Notacja z dużymi literami „O” mówi tylko o wydajności w limicie, gdy wielkość wejściowa przechodzi w nieskończoność. Więc jeśli algorytm opiera się na założeniu, że nie znajdują się żadne listy z ponad elementami n dla pewnego dużego N, limit czasu wykonywania jako wielkości listy zbliża nieskończoność jest niezdefiniowane. Dlatego złożoność nie jest „O (cokolwiek)”.
fgp
1
 // 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;
        }
    }
}
Richa
źródło
1
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;
}

Użyj powyższej funkcji, aby wykryć pętlę na liście połączonych w java.

Aditya Parmar
źródło
2
Prawie taka sama jak moja odpowiedź powyżej, ale ma problem. Zgłasza wyjątek NullPointerException dla list z listami o nieparzystej długości (bez pętli). Na przykład, jeśli head.next ma wartość null, to sec.next.next wyrzuci NPE.
Dave L.
1

Wykrywanie pętli na połączonej liście można wykonać na jeden z najprostszych sposobów, co powoduje złożoność O (N) przy użyciu mapy skrótów lub O (NlogN) przy użyciu podejścia opartego na sortowaniu.

Przechodząc przez listę zaczynając od głowy, utwórz posortowaną listę adresów. Po wstawieniu nowego adresu sprawdź, czy adres już tam jest na posortowanej liście, co wymaga złożoności O (logN).

Abhinav
źródło
Złożoność tego apporacha to O (N log N)
fgp
0

Nie widzę żadnego sposobu, aby to zajęło określoną ilość czasu lub miejsca, oba wzrosną wraz z rozmiarem listy.

Korzystałbym z IdentityHashMap (biorąc pod uwagę, że nie ma jeszcze IdentityHashSet) i zapisywałbym każdy Węzeł na mapie. Zanim węzeł zostanie zapisany, wywołujesz na nim zawiera klucz. Jeśli węzeł już istnieje, masz cykl.

ItentityHashMap używa == zamiast .equals, dzięki czemu sprawdzasz, gdzie znajduje się obiekt w pamięci, a nie czy ma taką samą zawartość.

TofuBeer
źródło
3
Z pewnością nie jest możliwe, aby zajęło to określoną ilość czasu, ponieważ na samym końcu listy może znajdować się pętla, więc całą listę należy odwiedzić. Jednak algorytm Fast / Slow demonstruje rozwiązanie wykorzystujące stałą ilość pamięci.
Dave L.
Czy to nie odnosi się do jego zachowania asymptotycznego, tzn. Jest liniowym O (n), gdzie n jest długością listy. Naprawiono byłoby O (1)
Mark Robson
0

Mogę być strasznie spóźniony i nowy, aby poradzić sobie z tym wątkiem. Ale nadal…

Dlaczego nie można adresu węzła i wskazanego „następnego” węzła przechowywać w tabeli

Gdybyśmy mogli w ten sposób przedstawić tabelę

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)

Dlatego powstaje cykl.

Sztolni Ya
źródło
Twoje rozwiązanie nie spełnia wymogu „stałej ilości miejsca”.
Arnaud
0

Oto mój kod do uruchomienia.

To, co zrobiłem, to ujawnienie połączonej listy za pomocą trzech tymczasowych węzłów (złożoność przestrzeni O(1)), które śledzą łącza.

Ciekawym faktem jest to, że pomaga wykryć cykl na połączonej liście, ponieważ w miarę postępu nie spodziewasz się powrotu do punktu początkowego (węzła głównego), a jeden z tymczasowych węzłów powinien przejść do wartości zerowej, chyba że mają cykl, co oznacza, że ​​wskazuje na węzeł główny.

Złożoność czasowa tego algorytmu jest, O(n)a złożoność przestrzeni jest O(1).

Oto węzeł klasy dla listy połączonej:

public class LinkedNode{
    public LinkedNode next;
}

Oto główny kod z prostym przypadkiem testowym trzech węzłów, które ostatni węzeł wskazuje na drugi węzeł:

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

Oto prosty przypadek testowy trzech węzłów, które ostatni węzeł wskazuje na drugi węzeł:

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));
    }
}
Habib Karbasian
źródło
0

Ten kod jest zoptymalizowany i będzie generował wynik szybciej niż ten wybrany jako najlepsza odpowiedź. Ten kod pozwala uniknąć bardzo długiego procesu ścigania wskaźnika węzła do przodu i do tyłu, który nastąpi w następującym przypadku, jeśli zastosujemy się do „najlepszego” odpowiedz ”. Spójrz na suchą sekwencję poniższych, a zrozumiesz, co próbuję powiedzieć. Następnie spójrz na problem za pomocą podanej poniżej metody i zmierz nie. kroków podjętych w celu znalezienia odpowiedzi.

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

Oto kod:

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
}
Sarthak Mehra
źródło
Czy jesteś pewien, że daje to właściwy wynik we wszystkich sytuacjach? Jeśli uruchomisz ten algorytm na liście 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 3 -> ..., wierzę, że zwróci 4 jako głowę, podczas gdy chcesz 3.
Sunreef
Pytanie polega tylko na stwierdzeniu, czy istnieje pętla, czy nie. W takim przypadku pytanie będzie absolutnie działać poprawnie i uzyska pożądany wynik logiczny dla przypadku. Jeśli chcesz dokładnie węzła, z którego pętla się rozpoczęła, to zrobimy to trzeba dodać coś więcej do kodu, ale jeśli chodzi o uzyskanie wyniku, spowoduje to szybsze zakończenie.
Sarthak Mehra
Nie przeczytałeś poprawnie pytania: Jaki jest najlepszy sposób pisania, boolean hasLoop(Node first)który zwróciłby wartość prawda, jeśli dany Węzeł jest pierwszą listą z pętlą, a fałsz w przeciwnym razie?
Sunreef
Oto lista próbna dla twojej listy: pierwsza wartość oznacza wskaźnik do tyłu, a druga część oznacza wskaźnik do przodu. (1,1) - (1,3) - (2,3) - (2,5) - (3,5) - (3,7) - (4,7) - (4,4)
Sarthak Mehra
W rzeczywistości zdaję sobie teraz sprawę, że istnieją dwa sposoby zrozumienia pytania (lub przynajmniej widzę dwie różne interpretacje). Twój algorytm jest poprawny, jeśli szukasz tylko pętli. Ale myślałem, że pytanie brzmi, gdzie zaczyna się pętla.
Sunreef
0

Oto moje rozwiązanie w Javie

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;
}
Irshad ck
źródło
0

Możesz również użyć algorytmu żółwia Floyda, jak sugerowano w powyższych odpowiedziach.

Ten algorytm może sprawdzić, czy pojedynczo połączona lista ma zamknięty cykl. Można to osiągnąć przez iterację listy z dwoma wskaźnikami, które będą poruszać się z różną prędkością. W ten sposób, jeśli istnieje cykl, dwa wskaźniki spotkają się w pewnym momencie w przyszłości.

Zapraszam do zapoznania się z moim postem na blogu w strukturze danych list połączonych, w którym również zamieściłem fragment kodu z implementacją wyżej wspomnianego algorytmu w języku Java.

Pozdrowienia,

Andreas (@xnorcode)

xnorcode
źródło
0

Oto rozwiązanie do wykrywania cyklu.

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 
        }
vishwaraj
źródło
0

// połączona lista funkcji wyszukiwania pętli

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}
Sonu Mishra
źródło
-1

To podejście ma narzut miejsca, ale prostszą implementację:

Pętlę można zidentyfikować, przechowując węzły na mapie. I przed postawieniem węzła; sprawdź, czy węzeł już istnieje. Jeśli węzeł już istnieje na mapie, oznacza to, że lista połączona ma pętlę.

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;  
  }  
rai.skumar
źródło
Nie spełnia to podanej w pytaniu stałej ilości miejsca !
dedek
zgadzam się, że ma miejsce nad głową; to inne podejście do rozwiązania tego problemu. Oczywistym podejściem jest algorytm żółwia i harse.
rai.skumar
@ downvoter, pomocne byłoby również wyjaśnienie przyczyny.
rai.skumar
-2
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;

}
edst
źródło