如何判断链表中有无环

如何判断链表中有无环

 

单向链表中有环的话，如果我们对此链表进行遍历，则将无穷尽。因此有必要判断一个单向链表是否有环。

假如一个单向链表中存在环，如下图：（一个小矩形代表链表中的一个节点）

虚线箭头代表中间有无数节点。

 

 

先说算法，然后再来证明算法的正确性。

  以下算法可以判断一个单向链表中是否有环(不讨论详细数据结构，只简要说明。设结点的next域为指向下一结点的指针)：

/*  链表的头指针为h  */

if((NULL == h) || (NULL == h->next)) /* 头指针为空或者链表中只有一个节点，则无环，退出 */

{

              return 0;

}

 

p = q = h; /* 设p和 q 指针， 均指向头结点 */

while(1)

{

    p = p->next;

    q = (q->next)->next；

    if((NULL == p) || (NULL == q))

    {

        printf(“No Ringn”); /* 链表中无环， 退出 */

        return 0;

}

    if(p == q) /* 链表中有环 */

    {

       printf(“Ring occurred\n”);

       return 1;

}

}

可以看出，以上算法设置了两个指针p和q，他们分别以速度为1和2前进，如果到某一次循环发现他们相等，即都指向同一结点（空节点除外，以后讨论的节点都不包含空节点），则说明这个单向链表中存在循环。否则就是没有循环。

我们注意到，指针p和q分别以速度为1和2前进。如果以其它速度前进是否可以呢？

下面我主要讨论这个问题。

假设p和q分别以速度为v1和v2前进。如果有环，设指针p和q第一次进入环时，他们相对于环中第一个节点的偏移地址分别为a和b（可以把偏移地址理解为节点个数）。如上图。

这样，可以看出，链表有环的充要条件就是某一次循环时，指针p和q的值相等，就是它们相对环中首节点的偏移量相等。

我们设环中的结点个数为n,程序循环了m次。

由此可以有下面等式成立：(mod(n)即对n取余)

(a+m*v1)mod(n) = (b+m*v2) mod(n)

设等式左边mod(n)的最大整数为k1，等式右边mod(n)的最大整数为k2，则

(a+m*v1)-k1*n = (b+m*v2)-k2*n

整理以上等式：

m= |((k2-k1)*n+a-b)/( v2-v1)|       ①

如果是等式①成立，就要使循环次数m为一整数。显然如果v2-v1为1，则等式成立。

这样p和q分别以速度为v1和v2且|v2-v1|为1时，按以上算法就可找出链表中是否有环。