# 描述
判断给定的链表中是否有环，如果有环则返回true，否则返回false。
要求：空间复杂度O(1) 时间复杂度O(n)
# 示例1
输入：{3,2,0,-4},1
返回值：true
说明：第一部分 {3,2,0,-4} 代表一个链表，第二部分1表示，-4到位置1，即-4 —> 2存在一个链接，组成传入 的head为一个带环的链表，返回为true
1
2
3
2
3
# 快慢指针
# 思路以及算法
这种算法又称龟兔赛跑算法，假设「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑的慢，当「乌龟」和「兔子」从链表上的同一个节点开始移动时候，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方，如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动，等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与「乌龟」相遇，即套了「乌龟」若干圈。
我们可以根据上述思想来解决本题，具体地，我们定义两个指针，一快一慢，慢指针每次只移动一步，而快指针每次移动两步，初始化时候慢指针在位置head，而快指针在位置head.next, 这样一来，如果在移动过程中，快指针反过来追上慢指针，就说明该链表为环形链表，否则快指针将达到链表尾部，该链表不为环形链表。
# 细节
为什么我们要规定初始时慢指针指向 head ，快指针的位置在 head.next 而不是都在head（即与「乌龟」和「兔子」中的位置相同？）
因为我们使用的是while循环，循环条件先于循环体，由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始化都置于head，那么while循环就不会执行，因此，我们可以假想一个在head之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next。这样我们就可以使用 while 循环了
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
// 判空条件先行
if(head === null || head.next === null) {
return false;
}
// 设置两个指针 为了保证赋值的有效性
// 所以上面需要做一个判空处理，防止空指针异常
let slow = head;
let fast = head.next;
// 这里使用while循环，循环体优先于循环条件
while(slow !== fast) {
// 为什么判断了快指针？因为快就能更快的到达目标阶段
// 快指针走到了链表的尾部，没有进入环，说明不存在环
if(fast === null || fast.next === null) {
return false;
}
slow = slow.next;
// 快一步
fast = fast.next.next;
}
return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
- 1206 复习 在重新看到题目的时候，空间复杂度的要求是O(1), 说明是不能使用额外的数据结构,知道这道题目使用的快慢指针的方法来解决。 这个题目，明天再写一遍。