判断数组链表环相关算法

一般需求如下：

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;

遍历设置标记位，当要遍历的值跟设置的值相同那么有环，反之无环;