Поиск цикла в одиночном списке с javascript (эффективное решение)

Question

Мое решение хорошо работает, если исходный узел правильно передан функции. Я хочу знать, является ли мое решение хорошим и эффективным. Я должен иметь возможность возвращать true, если цикл существует через функцию, которой первый узел передается как параметр. Я хотел бы знать, эффективно ли мое решение, особенно для настройки интервью. Мои комментарии в коде сами по себе. Я использую переменную дорожку для прохождения по списку и проверки нулевого значения или заголовка в качестве следующего. Если я сталкиваюсь с каким-либо из них обходами, а затем в отдельности проверяю состояние null или head и на основании этого возвращаю соответствующее логическое значение.

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 но главная идея состоит в том, что при перемещении одного указателя в два раза быстрее, чем другой указатель, то цикл будет идентифицировать как быстрый указатель будет в конечном итоге догнать другие , Вот возможное решение в 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; 

}