巧妙！如何检测一个链表是否有环？

巧妙！如何检测一个链表是否有环？

题目：如何检测一个链表中，是否存在环形？就像下图所示：

能够直接想到的方法，就是:

创建一个 hashtable，用于记录链表中的节点地址。然后开始遍历这个链表，对每个节点，查找其地址是否存在于 hashtable 中，如果存在，则认为产生了环形，算法结束。如果不存在，把这个节点的地址添加到 hashtable 中，继续判断下一个节点。

如果遍历完链表，就认为没有环形，算法结束。

上述算法，对于一个比较长的链表，需要消耗大量的内存来存储 hashtable，并且查找和添加操作都需要消耗 cpu 时间，因此不是一个好的算法。

下面介绍一个比较巧妙的算法：

用两个指针，同时开始遍历这个链表。这两个指针的区别是步进速度不一样。一个指针叫快指针，一次前进 2 个节点；另一个指针叫慢指针，一次前进一个节点。

如果链表中存在环形，则快指针和慢指针最终都会进入到环中。由于他们的速度不同，因此再过一段时间后，他们一定在环中的某个位置相遇。也就是说，这两个指针会相等。出现这种情况，就能判定链表有环。

如果快指针遍历完链表，就认为链表无环，算法结束。

用图示意如下：

用 C 语言实现的代码如下：

int list_has_cycle(list_t* plist) {    list_node_t* pfast = plist->phead;    list_node_t* pslow = plist->phead;
    while (pfast && pfast->pnext) {        pfast = pfast->pnext->pnext;        pslow = pslow->pnext;
        if (pfast == pslow) {            return 1;   // found cycle        }    }
    return 0;}

我的微信号是 实力程序员，欢迎大家关注我。