链表是否有环：Linked List Cycle

链表是否有环：Linked List Cycle

方法：使用快慢指针：

证明：慢指针跑过的路径为s1=a+b+x*circle (x为慢指针跑的圈数)

快指针跑过的路径为s2=2*s1=a+b+y*circle (y为快指针跑的圈数) 

两式相减得到:a+b =(y-2x)*circle

也就是只要存在y、x满足上式，就一定存在相遇点。

因为b < circle，不难推理出y、x一定存在。

链表是否有环II：Linked List CycleII

找出环开始的节点

方法：在上一题的基础上，相遇后，使用两个指针，一个指向head，一个指向当前相遇节点，分别每次前进一步，知道相遇。

证明：由上一题可以证明，存在y、x满足

a + b =  (y - 2x) * circle

由此可得出，必然存在z，使得：

a + b = (z + 1) circle

即：

a = z*circle + ( circle - b )

即：

a = z*circle + c

所以上式一定成立，两个指针一定会相遇在环开始的节点，相遇时开始时指向当前相遇节点跑了z圈。