javascriptを使用した単一リンクリストのサイクルの検索（私のソリューションは効率的です）

Question

開始ノードが関数に正しく渡されていれば、私のソリューションはうまく動作します。私の解決策が良いと効率的であるかどうかを知りたい。最初のノードがパラメータとして渡される関数を介してサイクルが存在する場合はtrueを返すことができます。私の解決策がインタビューのために特に有効かどうかを知りたい。コード内の私のコメントは自明です。私は可変トラックを使ってリストをたどり、次のものとしてヌルか頭をチェックします。もし私がそれらのいずれかに遭遇した場合、トラバース終了し、個別に私はnullまたは頭の状態をチェックし、それに基づいて適切なブール値を返します。

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

あなたはhttps://en.wikipedia.org/wiki/Cycle_detectionでサイクル検出の詳細を読むことができますが、主なお持ち帰りはあなたが別のポインタ2倍の速1つのポインタを移動した場合、高速ポインタは最終的に他に追いつくだろうと、ループが識別できるだろうということです。ここに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; 

}