Given a linked list, determine if it has a cycle in it.
判断一个链表是否有环？
Follow up:
Can you solve it without using extra space?
最好不用额外的空间得出答案
解：
循环链表的特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。
之前不理解为什么快慢指针会相遇，看了知乎冯昱尧的回答明白，答案如下：
这个问题你可以用数学归纳法来思考。首先，由于链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。那么做如下思考：
- 快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
- 快指针与慢指针之间差两步。此时唏嘘往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
- 快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。
因此，此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。
自己想了一个让自己能想明白的例子：
假设有一个环形跑道，A 和 B 跑步， A 一分钟跑完一圈，B 两分钟跑完一圈，那么在 A 跑完第二圈的时候 A 和 B 就会相遇；
如果是一条直直的跑道，A 和 B 就不可能相遇
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
var slow = head, fast = head;
while(true){
if(fast === null || fast.next === null){
return false;
}
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
return true;
}
}
};
