首页 文章

使用javascript在单链表中查找循环（我的解决方案是否有效）

提问于
浏览 次
0

如果正确地将起始节点传递给函数，我的解决方案很有效 . 我想知道我的解决方案是否良好和有效 . 如果循环存在于第一个节点作为参数传递的函数，我应该能够返回true . 我想知道我的解决方案是否有效，尤其是面试环境 . 我在代码中的评论是自我解释的 . 我使用可变轨道遍历列表并检查null或head作为下一个 . 如果我遇到任何遍历结束，然后单独检查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
javascript linked-list

1 回答

  • 0

    您可以在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;

    }

    回复于

相关问题