环形链表

leetcode141:环形链表
题目：

给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。 链接：https://leetcode-cn.com/problems/linked-list-cycle

方法一：new Set()方法

思路：定义一个cache的变量，数据类型为Set，Set为es6新增的数据类型，会自动去重，Set集合中的每个值是唯一的。遍历head中的每个节点，使用Set的has方法判断Set中是否有该值，如果有，说明环形链表，返回true；否则使用Set的add方法，将该值添加到Set中继续遍历，如果遍历完节点值也没有重复的，那么返回false。

复杂度： 时间复杂度：O(n）空间复杂度：O(n)

代码：

var hasCycle = function(head){
    let cache = new Set()
    while(head){
        if(cache.has(head)){
            return true
        }else{
             cache.add(head)
        }
        head = head.next
    }
    return false
}

方法二： 快慢指针 （经典解法）

原理： 龟兔赛跑原理（快慢指针原理）
众所周知，🐰比🐢跑的慢，他们位于同一起跑点开始跑，如果不是环形链表，那么🐰永远在🐢前面。如果是环形链表，那么当🐰领先🐢很多圈的时候，某一点🐰和🐢会相遇。那么在这一点判断值是否相等，相等则为环形链表。也称为快慢指针，定义两个指针，一个是快指针代表🐰，一个是慢指针🐢。

复杂度： 时间复杂度：O(n) 空间复杂度： O(1)

代码：

var hasCycle = function(head){
    let slow = head
    let fast = head
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
        if(slow === fast){
            return true
        }
    }
    return false
}