如何判断一个单单向链表是否有環环

有环返回进入环的第一个节点，无环返回空

时间复杂度O(N),额外空间复杂度O(1)

* 无重复则不存在环点

* 有重复则将快指针从头单位步长执行慢指针从之前重复位置执行

* 再次重合位置为入环位置

版权声明：本文为博主原创文章未经博主允许不得转载。 /sinat_/article/details/

如图如果单链表有环，则在遍历时在通过6之后，会重新回到3那么我们可以在遍历时使用两个指针，看两個指针是否相等

方法一：使用p、q两个指针，p总是向前走但q每次都从头开始走，对于每个节点看p走的步数是否和q一样。如图当p从6走箌3时，用了6步此时若q从head出发，则只需两步就到3因而步数不等，出现矛盾存在环

方法二：使用p、q两个指针，p每次向前走一步q每次向湔走两步，若在某个时候p == q则存在环。