Wie erkennt man eine Schleife in einer verknüpften Liste?

Question

Angenommen, Sie haben eine verknüpfte Listenstruktur in Java. Sie besteht aus Nodes:

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

und jeder Knoten verweist auf den nächsten Knoten, mit Ausnahme des letzten Knotens, bei dem der nächste Knoten Null ist. Angenommen, es besteht die Möglichkeit, dass die Liste eine Schleife enthält - d. h. der letzte Knoten hat statt einer Null einen Verweis auf einen der Knoten in der Liste, der vor ihm lag.

Was ist die beste Art zu schreiben?

boolean hasLoop(Node first)

die Folgendes zurückgeben würde true wenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, und false sonst? Wie könnte man so schreiben, dass der Platzbedarf gleich bleibt und die Zeit angemessen ist?

Das folgende Bild zeigt, wie eine Liste mit einer Schleife aussieht:

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

Verwenden Sie die obige Funktion, um eine Schleife in einer verknüpften Liste in Java zu erkennen.

Answer 2

Ich bin mir nicht sicher, ob diese Antwort auf Java anwendbar ist, aber ich denke, sie gehört trotzdem hierher:

Wann immer wir mit Zeigern auf modernen Architekturen arbeiten, können wir erwarten, dass sie CPU wortorientiert . Und für eine 64-Bit-Architektur bedeutet dies, dass die ersten 3 Bits in einem Zeiger immer Null sind. So können wir diesen Speicher zum Markieren von Zeigern verwenden, die wir bereits gesehen haben, indem wir 1 in ihre ersten Bits schreiben.

Und wenn wir auf einen Zeiger stoßen, dessen erstes Bit bereits eine 1 enthält, dann haben wir erfolgreich eine Schleife gefunden. Geschafft!

Dieser Ansatz wird als Pointer-Tagging und wird in der Low-Level-Programmierung exzessiv verwendet, z.B. Haskell verwendet es für einige Optimierungen .

Answer 3

Wenn die Struktur der verknüpften Liste java.util.List implementiert. Wir können die Listengröße verwenden, um unsere Position in der Liste zu verfolgen.

Wir können die Knoten durchlaufen, indem wir unsere aktuelle Position mit der Position des letzten Knotens vergleichen. Wenn unsere aktuelle Position die letzte Position übertrifft, haben wir festgestellt, dass die Liste irgendwo eine Schleife enthält.

Diese Lösung benötigt eine konstante Menge an Speicherplatz, hat aber den Nachteil, dass die Zeit für die Fertigstellung mit zunehmender Listengröße linear ansteigt.

class LinkedList implements List {
    Node first;
    int listSize;

    @Override
    int size() {
        return listSize;
    }

    [..]

    boolean hasLoop() {
        int lastPosition = size();
        int currentPosition = 1;
        Node next = first;
        while(next != null) {
           if (currentPosition > lastPosition) return true;
           next = next.next;
           currentPosition++;
        }
        return false;
    }
}

Oder als Dienstprogramm:

static boolean hasLoop(int size, Node first) {
    int lastPosition = size;
    int currentPosition = 1;
    Node next = first;
    while(next != null) {
       if (currentPosition > lastPosition) return true;
       next = next.next;
       currentPosition++;
    }
    return false;
}

Answer 4

// Suchschleifenfunktion für verknüpfte Listen

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

Answer 5

Ich sehe keine Möglichkeit, dafür eine feste Zeit- oder Speicherplatzvorgabe zu machen, beides wird mit der Größe der Liste zunehmen.

Ich würde eine IdentityHashMap verwenden (da es noch kein IdentityHashSet gibt) und jeden Knoten in dieser Map speichern. Bevor ein Knoten gespeichert wird, würde man ihn mit containsKey aufrufen. Wenn der Knoten bereits existiert, haben Sie einen Zyklus.

ItentityHashMap verwendet == anstelle von .equals, so dass überprüft wird, wo sich das Objekt im Speicher befindet, und nicht, ob es den gleichen Inhalt hat.