Wie Sie feststellen, ob eine verknüpfte Liste einen Zyklus mit nur zwei Speicherplätze hat

Question

Kennt jemand einen Algorithmus zu finden, wenn eine verknüpfte Liste auf sich selbst Schleifen nur zwei Variablen, die Liste zu durchqueren. Sagen Sie bitte eine verknüpfte Liste von Objekten, es spielt keine Rolle, welche Art von Objekt. Ich habe einen Zeiger auf den Kopf der verketteten Liste in einer Variablen, und ich bin nur eine andere Variable gegeben, um die Liste mit zu durchqueren.

So ist mein Plan Zeigerwert zu vergleichen, um zu sehen, ob alle Zeiger gleich sind. Die Liste ist von endlicher Größe, sondern kann sehr groß sein. Ich kann sowohl Variable auf den Kopf gesetzt und dann die Liste mit den anderen Variablen durchquert, überprüft immer, wenn es gleich den anderen variabel ist, aber, wenn ich eine Schleife zu tun getroffen werde ich nie herausbekommen. Ich denke, es mit unterschiedlichen Raten zu tun hat, um die Liste zu durchqueren und Zeigerwerte zu vergleichen. Irgendwelche Gedanken?

Answer 1

Ich würde vorschlagen, Floyd's Cycle-Finding Algorithm mit aka Die Tortoise and the Hare Algorithm. Es hat O (n) Komplexität und ich denke, dass es Ihre Anforderungen entspricht.

Beispielcode:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Weitere Informationen über Wikipedia. Floyds Zyklus-Suchalgorithmus

Answer 2

Sie können über die Schildkröte und Kaninchen Algorithmus.

Wikipedia hat auch eine Erklärung, und sie nennen es „ Floyds Zyklus-Suchalgorithmus “oder "Schildkröte und Hase"

Answer 3

Auf jeden Fall. Eine Lösung in der Tat können die Liste mit beiden Zeiger werden durchquert, eine mit der doppelten Geschwindigkeit des anderen Reisen.

Beginnen Sie mit dem ‚langsam‘ und der ‚schnellen‘ Zeiger, der auf einer beliebigen Stelle in der Liste. Führen Sie die Traversal-Schleife. Wenn der ‚schnellen‘ Zeiger jederzeit mit dem langsamen Zeiger übereinstimmen kommt, haben Sie eine kreisförmige verkettete Liste.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

Answer 4

Ich habe versucht, mich zu lösen und fand eine andere (weniger effizient, aber immer noch optimal) Lösung.

Die Idee zugrunde, eine einfach verkettete Liste in linearer Zeit auf Umkehren. Dies kann, indem Sie zwei Swaps bei jedem Schritt in iteriert über die Liste erfolgen. Wenn q das vorherige Element (anfänglich null) ist, und p der Strom ist, dann tauschen (q, p-> next) swap (p, q) den Link und bewegen sich die beiden Zeiger in der gleichen umzukehren. Die Swaps können XOR durchgeführt werden unter Verwendung zu verbieten, einen dritten Speicherplatz zu verwenden.

Wenn die Liste einen Zyklus hat dann an einem Punkt während der Iteration werden Sie an einem Knoten, dessen Zeiger ankommen bereits geändert wurde. Sie können nicht wissen, welche Knoten, der ist, aber durch die Iteration fortgesetzt, einige Elemente zweimal tauschen, kommt man an der Spitze der Liste wieder.

die Liste zweimal Durch Umkehrung der Liste bleibt unverändert in Folge und man kann sagen, ob es einen Zyklus hatte basierend darauf, ob Sie an der ursprünglichen Spitze der Liste angekommen ist oder nicht.

Answer 5

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}

Answer 6

boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}

Answer 7

Unter diesem Problem zu einem nächsten Schritt wird sein, den Zyklus zu identifizieren (das heißt, nicht nur, dass der Zyklus existiert, aber wo genau ist es in der Liste). Schildkröte und Hasen-Algorithmus kann für die gleichen verwendet werden, jedoch werden wir benötigen, um zu verfolgen die Spitze der Liste zu allen Zeiten. Eine Darstellung dieses Algorithmus kann hier zu finden .