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

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ą:

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

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
}

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

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

Żół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ł.)

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

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.

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

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)

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

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.

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

}

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ę.

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

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.

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).

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ść.

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.

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

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
}

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

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)

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 
        }

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

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

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;

}