Linked List Cycle

问题

判断链表中是否有环，如果有，找出链表中环的起始节点

解决

首先找出环的话可以用快慢节点法，快节点的速度是2，慢节点是1 因为两个节点进入环后，快节点会以2-1=1的速度接近慢节点，所以如果有环的话，两节点一定会相遇，否则快节点会先到链尾

接下来就是寻找环的起始节点，根据下图我们有：

2(t+x)=t+x+n(x+y)
t=(n-1)(x+y)+y

x+y就是环的长度，换句话说，t就是环长的整数倍+y，那么我们在快慢节点相遇后，再设置一个慢节点到链头，他们第一次相遇的时候，一定在t处，也就是环节点了

Tips

• 结论非常好记，就两个，首先快慢节点判断环，第二相遇后加一个慢节点判断环起始位置，证明也只是用代数式推一下而已，可以只记结论
• 算环长的话，知道环的起始位置，自然而然也就知道环的长度了（再加个不动点）