美文网首页让前端飞前端开发那些事儿
前端javascript面试判断单链表是否有环

前端javascript面试判断单链表是否有环

作者: 一一秋风 | 来源:发表于2020-12-08 17:45 被阅读0次
    1. 创建哈希表,不过会占⽤较⼤的空间,不是最佳⽅法.( 时间复杂度O(n) )
    function judge(list){
      var set =new Set();
      while(list){
        if(set.has(list)){
          return true
        }
        set.add(list)
        list=list.next()
      }
    }
    
    1. 给节点添加visited访问标记 (时间复杂度O(n)), 不需要额外的空间
    function LinkedList(){
      var Node=function(){
        this.element=element;
        this.next=null;
        this.visited=0; //访问标记
      }
    }
    
    function judge(list){
      while(list){
        if(list.visited==1){
         return true
        }
        list.visited=1
        list=list.next()
      }
    }
    
    1. 快慢指针法,设定快指针fast,慢指针slow,每次循环快指针fast移动两个位置,慢指针移动⼀个位置
      (时间复杂度 O(n)) 需要额外的空间
    function judge(list){
      var fast=list.next.next,
      slow=list.next;
      while(fast){
        if(fast===slow){
              return true
        }
        fast=fast.next.next
        slow=slow.next
      }
    }
    

    相关文章

      网友评论

        本文标题:前端javascript面试判断单链表是否有环

        本文链接:https://www.haomeiwen.com/subject/uerqgktx.html