【js刷题：数据结构链表之环形链表】
环形链表
- 一、题目
- 二、实现思路
- 1.判断是否有环
- 2.如何找到环状链表的入口节点
- 三、解题代码
一、题目
二、实现思路
主要有两点，首先我们要判断这个链表是否有环，其次我们要找到这个环的入口节点。
1.判断是否有环
定义一个快指针fast和慢指针slow
快指针每次移动两个节点，慢指针移动一位，那么如果快指针最终会与慢指针相遇，则说明这个链表有环，并且一定是在环内相遇（fast移动的长度是slow的两倍，相遇时fast一定是在环内，直线不会相遇）
2.如何找到环状链表的入口节点
设慢节点移动（x+y)*2（注：快指针的移动长度是慢指针的两倍）,快节点移动x+y+n(z+y)后相遇
则（x+y）*2=x+y+n(z+y)
我们最终要通过x求到环状入口节点，所以将x移动到左边，得：
x=n(z+y)-y
再从n(y+z)中提出一个 （y+z）来，整理后得：x = (n - 1) (y + z) + z (注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。)
这个公式意味着定义两个节点一个节点从头节点出发，另一个节点在指针相遇处出发，那么最终他们相遇的地方就是链表环状的入口节点。
三、解题代码
