document.write('

方法一:蛮力法 定义一个HashSet用来存放结点的引用,并将其初始化为空,从链表的头结点开始向后遍历,每遍历 到一个结点就判断HashSet中是否有这个结点的引用,如果没有,说明这个结点是第一次访问,还没有 形成环,那么将这个结点的引用添加到指针HashSet中去。如果在HashSet中找到了同样的结点,那么 说明这个结点已经被访问过了,于是就形成了环。这种方法的时间复杂度为O(N),空间复杂度也为 O(N)。

方法二:快慢指针遍历法 定义两个指针fast(快)与slow(慢),二者的初始值都指向链表头,指针slow每次前进一步,指针fast每 次前进两步,两个指针同时向前移动,快指针每移动一次都要跟慢指针比较,如果快指针等于慢指针, 就证明这个链表是带环的单向链表,否则,证明这个链表是不带环的循环链表。实现代码见后面引申部 分。

');