有赞&leetcode141：判断一个单链表是否有环 #13

Activity

1. hhshii commented on Apr 10, 2020

   

   hhshii

   on Apr 10, 2020

   More actions

   当然是让引擎帮你判断啦

   function hasLoop(node){
   	try{
   		JSON.stringify(node)
   	}catch(e){
   		return e.toString().includes('Converting circular')
   	}
   	return false
   }

   哈哈哈开玩笑的，其实可以用 Map 或者快慢指针解

   👍React with 👍3Reacted by Bean, Jerry and Jin Yao

   👎React with 👎2Reacted by Eden and xingyu

   😄React with 😄8Reacted by 瓶子君, 阿五, cha!, Bean, 野草, Zale, (^_^) and lanbo
2. sisterAn commented on Apr 10, 2020

   

   sisterAn

   on Apr 10, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法一：标志法

   给每个已遍历过的节点加标志位，遍历链表，当出现下一个节点已被标志时，则证明单链表有环

   let hasCycle = function(head) {
       while(head) {
           if(head.flag) return true
           head.flag = true
           head = head.next
       }
       return false
   };

   时间复杂度：O(n)

   空间复杂度：O(n)

   解法二：利用 JSON.stringify() 不能序列化含有循环引用的结构

   let hasCycle = function(head) {
       try{
           JSON.stringify(head);
           return false;
       }
       catch(err){
           return true;
       }
   };

   时间复杂度：O(n)

   空间复杂度：O(n)

   解法三：快慢指针（双指针法）

   设置快慢两个指针，遍历单链表，快指针一次走两步，慢指针一次走一步，如果单链表中存在环，则快慢指针终会指向同一个节点，否则直到快指针指向 null 时，快慢指针都不可能相遇

   let hasCycle = function(head) {
       if(!head || !head.next) {
           return false
       }
       let fast = head.next.next, slow = head.next
       while(fast !== slow) {
           if(!fast || !fast.next) return false
           fast = fast.next.next
           slow = slow.next
       }
       return true
   };

   时间复杂度：O(n)

   空间复杂度：O(1)

   leetcode

   👍React with 👍7Reacted by Bean, juggle2729, Zale, hoel, doubleaaseven, Wei Mingye and arieslx
3. 13001920223 commented on Apr 23, 2020

   

   13001920223

   on Apr 23, 2020

   More actions

   哈希map
   init一个WeakMap用来存放已经遍历的链表，判断如果不存在set, 如果存在则是循环引用

   var hasCycle = function(head) {
     let map = new WeakMap()
     if (!head && !head.next) {
       return false
     }
     while (head) {
       if (map.get(head)) {
         return true
       } else {
         map.set(head, false)
         head = head.next
       }
     }
     return false
   };

   👍React with 👍5Reacted by 冯淼森, Miss Chen, 前端胖头鱼, faseng and 小撸
4. sisterAn

   added

   LeetCode

   有赞

   on May 5, 2020
5. Been101 commented on Jul 15, 2020

   

   Been101

   on Jul 15, 2020

   More actions

   function Node(data) {
     this.data = data
     this.next = null
   }
   
   const node1 = new Node(1)
   const node2 = new Node(2)
   const node4 = new Node(4)
   const node6 = new Node(6)
   
   const node3 = new Node(3)
   const node5 = new Node(5)
   const node9 = new Node(9)
   
   node1.next = node2
   node2.next = node4
   node4.next = node6
   
   node6.next = node5
   node5.next = node9
   node9.next = node6
   
   
   let hasCycle = function (head) {
     if (!head || !head.next) {
       return false
     }
     let fast = head.next.next,
       slow = head.next
     let i = 0
     while (fast !== slow) {
       if (!fast || !fast.next) {
         return false
       }
       fast = fast.next.next
       slow = slow.next
       i++
     }
     return true
   }
   
   const hasCycle2 = (head) => {
     try {
       JSON.stringify(head)
       return false
     } catch (error) {
       console.log(error)
       return true
     }
   }
   
   const hasCycle3 = (head) => {
     let link = head
     while (link) {
       if (link.flag) return true
       link.flag = true
       link = link.next
     }
     return false
   }
   
   var a = hasCycle3(node1)

   👍React with 👍1Reacted by lanbo