让前端飞前端开发那些事儿

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

2020-12-08  本文已影响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
  }
}
上一篇下一篇

猜你喜欢

热点阅读