怎样判断链表有没有环

假设序列X0, X1, X2, ...是由X(n+1) = f(Xn)定义的, 如果f的值域是有限, 那么序列必定是循环的. 也就是说，这个序列包含一个前导（前缀）序列: X0, X1, ... X(u-1), 后面跟着一个不受限制的循环: Xu, X(u+1), ..., X(u+t-1), 其中t是循环的周期.

这个结论可以由抽屉原理推导出来: 即N+1个苹果放在N个屉子里, 至少有一个屉子至少有2个或以上的苹果. 对于X(n+1) = f(Xn)来说, 如果Xn和X(n+t-1)是相同的, 那么它们的后继也就是相同的, 也就是出现环了.

在随机数的生成以及检测连表的循环方面，都是相同的问题。

对于单连表而言，可以定义函数：

int f(int x)
{
    return (x)? ((Node*)x)->next: head;
}

即，假设连表到尾部之后再调用f就从头开始, 这样我们测试f的循环周期, 如果周期比连表长度短肯定是是有内部循环.

R.W.Floyd算法可以描述为：

x = f(x)
y = f(f(y))

其中，xy被初始化为X0。经过n步之后，x = Xn, y = X2n。比较这些元素，如果相等，那么就知道Xn和X2n之间的间隔是周期t的整数倍，即2n-n=n是t的倍数。

于是u就可以通过重新生成序列并比较X0和Xn, X1和X(n+1), 等等来确定. 当Xu和X(u+n)相比较相等的情况.

最后, 通过重新生成更多的元素并把Xu和X(u+1), X(u+2), … 相比较来确定周期t.

这个算法仅需要较小且有界的空间, 但是它要多次计算f。

Gosper的算法寻找f的周期t, 但不求第一次循环开始点u. 他的主要特征是从不回头去重新计算f, 而且在空间和时间上相当经济.

它所用的空间是无界的: 它需要一个长度为log2(max(t))+1的表, 其中max(t)是最大可能的周期. 这不会需要太多的空间.

例如: 如果是针对32位二进制, 那么33个字就足够了.

Gosper算法的C实现如下:

void ld_Gosper(int (*f)(int), int X0,
            int *mu_l,int *mu_u, int *lambda)
{
    int Xn, k, m, kmax, n, lgl;
    int T[33];

    T[0] = X0;
    Xn = X0;
    for (n = 1; ; n++) {
        Xn = f(Xn);
        kmax = 31 - nlz(n);           // Floor(log2 n).
        for (k = 0; k <= kmax; k++) {
            if (Xn == T[k]) goto L;
        }
        T[ntz(n+1)] = Xn;             // No match.
    }

L:
    // Compute m = max{i | i < n and ntz(i+1) = k}.

    m = ((((n >> k) - 1) | 1) << k) - 1;
    *lambda = n - m;
    lgl = 31 - nlz(*lambda - 1); // Ceil(log2 lambda) - 1.
    *mu_u = m;                       // Upper bound on mu.
    *mu_l = m - max(1, 1 << lgl) + 1;// Lower bound on mu.
}

该函数以需要分析的函数f和初始值X0为参数。它返回u的上界和下界以及周期t（尽管Gosper算法不能计算u，但它能计算u的上界和下界）。

函数中还用到了3个子函数：nlz, ntz, max.

其中nlz是求二进制前缀0的数目，ntz是计算二进制后缀0的数目， max求最大值（不用详细描述）。下面给出nlz和ntz的实现代码。

int nlz(unsigned x)
{
    int n;

    if (x == 0) return(32);
    n = 1;
    if ((x >> 16) == 0) {n = n +16; x = x <<16;}
    if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
    if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
    if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
    n = n - (x >> 31);
    return n;
}

int ntz(unsigned x)
{
    int n;

    x = ~x & (x - 1);
    n = 0;                       // n = 32;
    while(x != 0) {              // while (x != 0) {
        n = n + 1;                //    n = n - 1;
        x = x >> 1;               //    x = x + x;
    }                            // }
    return n;                    // return n;
}

其中计算后缀0数目的函数ntz有的地方也叫标尺函数，因为通过它给出了标尺上的二等份、四等份、…

标尺函数可以揭示出如何解汉诺塔之谜。标尺函数还可以用于生成反射二进制Gray编码。

关于Gosper的讨论可以参考Knuth, Donald E的经典著作：《计算机程序设计的艺术》卷2，3.1节的习题7。

文章目录