Einen Zyklus in einer einfach verknüpften Liste mit Javascript finden (Ist meine Lösung effizient)

Question

Meine Lösung funktioniert gut, wenn der Startknoten korrekt an die Funktion übergeben wird. Ich möchte wissen, ob meine Lösung gut und effizient ist. Ich sollte in der Lage sein, wahr zurückzugeben, wenn der Zyklus über eine Funktion existiert, an die der erste Knoten als Parameter übergeben wird. Ich würde gerne wissen, ob meine Lösung besonders für ein Interview geeignet ist. Meine Kommentare im Code sind selbsterklärend. Ich benutze eine variable Spur, um durch die Liste zu gehen und nach einer Null oder einem Kopf als nächstes zu suchen. Wenn ich auf eines der Traversal-Enden stoße und dann einzeln auf Null oder Head-Zustand überprüfe, gebe ich den entsprechenden booleschen Wert zurück.

function SLLNode(elem) { 
    this.value=elem; 
    this.next=null; 
} 

var hasCycle=function(node){ 

    var track=node; 
    //traverse thru list till next node is either null or back to first node 
    while(track.next!==null && track.next!==this.head){ 
     track=track.next; 
    } 
    if(track.next === null){ //if next node null then no cycle 
     return false; 
    } 
    if(track.next===this.head){ //if next node head then there is cycle 
     return true; 
    } 
} 

var my_node1=new SLLNode(3); 
var my_node2=new SLLNode(5); 
var my_node3=new SLLNode(19); 

//assigning head 
var head=my_node1; 

//connecting linked list 
my_node1.next=my_node2; 
my_node2.next=my_node3; 
my_node3.next=my_node1; //cycle 
console.log("Has cycle?: "+hasCycle(my_node1)); //outputs true as expected 

var node1=new SLLNode(3); 
var node2=new SLLNode(5); 
var node3=new SLLNode(19); 

//assigning head 
var head1=node1; 
node1.next=node2; 
node2.next=node3; 
console.log("Has cycle?: "+hasCycle(node1)); //outputs false as expected 

Answer 1

Sie können https://en.wikipedia.org/wiki/Cycle_detection mehr auf Zyklus-Erkennung lesen, aber die Haupt zum Mitnehmen ist, dass, wenn Sie einen Zeiger doppelt so schnell wie ein anderer Zeiger bewegen dann eine Schleife identifizierbar sein würde, wie der schnelle Zeiger wird schließlich mit dem anderen aufholen . Hier ist eine mögliche Lösung in js.

function hasCycle(head) { 
    var slow, fast; 

    if(!head || !head.next) return false; 

    slow = head; 
    fast = head; 

    if(head.next === head) return true; 

    while(fast.next.next) { 

     slow = slow.next; 
     fast = fast.next.next; 

     if(slow === fast) return true; 
    } 

    return false; 

}