检测并定位链表中的环

Contents

1. 1. 算法解析
2. 2. 定位环起点
3. 3. 相关代码
   1. 3.1. 节点定义
   2. 3.2. 检测与定位函数
   3. 3.3. 测试主函数

　　之前一篇写了如何反转链表以及定位链表的中点，现在来一个稍微复杂点的问题。

　　这个面试题是我第一次参加实习生笔试时遇到的，当时并没有解出来。题目要求是检测单向链表是否存在环，并且只用常数的额外存储空间。

　　简单直接的办法自然是将每一个指针记录下来，并且和新出现的节点的next指针比较，如果next指向之前出现过的节点，说明有环。但是这种方法需要至少线性的空间，不符合题目要求。而且每次都需要查找比较，性能很低。或者使用hash表，则空间消耗较list更大。

　　出来之后我就开始搜索了，解法很好懂，但是如果没有学习过相关算法，要靠自己想出来还是挺有难度的。

　　解法的奥秘全在下面这张图里了。

算法解析

　　解法相当简单：两个指针同时从头部出发，normal以每步1节点的速度向前移动，fast以两倍速移动，如果二者相遇，则说明存在环。

　　设计得相当巧妙。有人问有没有可能第一次刚好越过而没有相遇呢？请自己简单分析一下，是不存在这种可能。

定位环起点

　　这已经不是面试题的要求了，属于扩展内容,需要用到上图标出的等式及其变形。

　　解释下上图中字母的含义，a是起点到环起点的距离，x为环起点到相遇点的距离，L为环周长，n为fast在环上移动的圈数。

　　等式如何来的，normal走了a+x, fast多走了nL,总里程是2倍的关系，所以a+x = nL;

　　变换一下是a = nL - x, a就是我们要定位的点的位置。

　　如何使用这个式子，也需要比较巧妙的设计:

1. normal从head往前走
2. fast继续从相遇点前移，但这次降为1倍速
3. 它们将在环起始点相遇

　　至于为什么，请再仔细参照上面的变形式。

相关代码

　　使用C实现，顺便熟悉下C语言。

节点定义

typedef struct Node {
    char *name;
    struct Node *next;
} Node;

检测与定位函数

　　无环返回0,有环返回环起始点指针：

Node *detectLoop(Node *head) {
    Node *fast = head, *normal = head;
    while (fast && fast->next) {
        normal = normal->next;
        fast = fast->next->next;
        if (fast == normal) {
            break;
        }
    }
    if (!fast) {
        return 0;
    } else {    //locate the beginning node of the loop
        normal = head;
        while (normal != fast) {
            normal = normal->next;
            fast = fast->next;
        }
        return normal;
    }
}

测试主函数

　　这里使用了一个如下结构的环：

　　以下是main()函数代码。

int main(int argc, char *argv[]) {
    Node node9 = {"9", 0}, node8 = {"8", &node9}, node7 = {"7", &node8},
        node6 = {"6", &node7}, node5 = {"5", &node6}, 
        node4 = {"4", &node5}, node3 = {"3", &node4}, 
        node2 = {"2", &node3}, node1 = {"1", &node2}, head = {"0", &node1};
    node9.next = &node4;
    Node *p = &head;
    int i = 0;
    while (p && i++ < 12) {
        printf("%s ", p->name);
        p = p->next;
    }
    printf("\n");

    Node *pNode = detectLoop(&head);
    if (pNode) {
        printf("The loop starts at: %s", pNode->name);
    } else {
        printf("There is no loop");
    }

    return 0;
}

　　运行结果 ：

0 1 2 3 4 5 6 7 8 9 4 5 
The loop starts at: 4

　　好的，测试完成。实质上，返回链表尾（9号结点）更有意义一些，稍作修改即可。