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

1. 创建哈希表,不过会占⽤较⼤的空间,不是最佳⽅法.( 时间复杂度O(n) )

function judge(list){
  var set =new Set();
  while(list){
    if(set.has(list)){
      return true
    }
    set.add(list)
    list=list.next()
  }
}

2. 给节点添加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()
  }
}

3. 快慢指针法,设定快指针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
  }
}