一般需求如下:
1.判断某链表中是否有环(某年研究生入学统招试题)?
2.判断某int[]是否有环,举例如下根据其值 array[i]=0时原地不走,相当于有环了;array[i]=-10,向后移动10步;array[i]=10向前走10步。当某停止点两次停止过那么算有环
分析:
在有足够空间的前提下都容易实现,在没有额外空间的前提下(变量不算),那么就需要思考了,题目2如果不是int而是一个object那么很容易,对object进行封装两个属性来标记是否访问过,同时题目1也适用,我们可以对访问过的节点设置某值来区分是否访问过,也可以通过步长不等的指针遍历,当指针重合的时候代表有环,其实这两个题都适用。
思路1:
题目1和2均使用:
定义两个指针p1和p2,p1每次走1个单元,p2每次走2个单元(题目2的两次停顿);
当p1和p2重叠就代表有环,反之无环;
思路2:
定义一个指针,找一个固定值并且能区分其他节点值,当访问过了就设置标记位,来标记是否访问过,题目1看具体的需求,科目2设置成0;
遍历设置标记位,当要遍历的值跟设置的值相同那么有环,反之无环;