【木灵的程序工作室】数据结构的C/C++描述02.01：单链表环路检测算法

我们在上节已经讨论过，如果一个单链表中由于某种原因(数据错误、内存泄漏、测试人员瞎点等)存在了环路，那么所有基于next成员的遍历都会输出错误的结果或者出现死循环。避免这一问题的一个解决方案是通过插入次数来记录单链表的长度，在遍历时使用这个长度作为限制，来避免无限在环上跑圈儿，但是这种方法需要链表在整个生命周期内被链表类封装，但是，编码实践告诉我们，一般会出现环路异常的链表都是没有经过封装的链表，那么对于没有封装的链表的第二个方案就是：判断一个链表是否有环路并且找出这个环路。那么如何去检验一个链表存在环路呢？

我们的讨论都是基于以如下节点形成的链表：

template<class elementType>
struct node {
    elementType data;
    node<elementType> *next;
    node(elementType _data = 0, node<elementType>* _next = nullptr) : data(_data), next(_next) {}
    bool operator==(const node<elementType> &x) {
        return this->data == x.data && this->next == x.next;
    }
};

首先，由简单的逻辑思考可以知道：由于一个节点最多有一个指针，所以一个单链表最多只能存在1个圈，且有圈的链表没有表明终止的NULL指针，否则一定会有一个元素存在着两个next指针。这个圈是由于尾节点的next指针错误地指向了链表中的节点导致 (单链表的尾节点的next指针应当是nullptr，即空值)。

那么第一个判圈算法就很直观了：

遍历链表，记录遍历过的每一个链表节点的实例或者地址，当发现某一个节点的next指针指向了已经记录过的节点时，就可以得出有圈的结论；反之，如果发现某一个节点的next指针是nullptr，则得出无圈结论。
记录这个节点指针的方法可以使用数组或者散列。

那么实现一下：

朴素环路检测

template<class elementType>
bool isCircleInChain(node<elementType>* head) {
    unordered_map<node<elementType>*, bool> history;
    while(head != nullptr) {
        if (history.find(head) != history.end()) //“如果在history中找到了指针head的访问记录”
            return true;
        history[head] = 1;  //插入head的访问记录
        head = head->next;
    }
    return false;
}

对于长度为n的链表，这种算法使用了O(n)的渐近额外空间复杂度和O(n)的渐近时间复杂度。它的优势在于可以直接找出是哪一个节点的next指针发生了偏转导致圈的产生。（上述的程序不具备此功能，不仅是由于它的返回值不是指针类型，还由于它操作的指针是head而不是head->next）

Floyd环路检测

考虑一个现实情境：一个快车和一个慢车同时同地出发，在一个环形道路上不停行驶，快车一定有某一个时刻从后方追上并且超过慢车。我们使用这个情景带给我们的结论，将环形道路抽象为(可能带环的)链表，将两辆车抽象为两个指针，两个指针初始化为表头的位置，我们让快指针每次移动2(可以为任意大于1的数，但是为2时程序的编码最为简洁)个单元，慢指针每次移动1个单元，当我们发现快指针与慢指针相等时(在初始化时的相等不计)，即表明链表中存在环路；当我们访问了null指针时，即表明链表存在尽头，即没有环。

有的同学可能会有这种考虑：“如果快指针在接近慢指针时刚好跳过了它，那么判断不会失败吗？” 其实，如果快指针步数为2而慢指针步数为1，在上述“快指针在接近慢指针时刚好跳过了它”的情况发生之前的一个单位时间，快指针和慢指针必然是重合的；相似地，如果“快指针在接近慢指针时刚好在它的前一个”的情况发生之后的一个单位时间，快指针和慢指针将会重合。但是如果此处让快指针步进3，情况就会变得复杂。

也就是说，如果步长分别为2和1，那么只要慢指针进入了环路，在最差情况下慢指针只需要绕行一整圈才可以得出结果，而最优情况是慢指针进入环就可以得出结果。所以对于一个总长为n的链表，这个算法的渐进时间复杂度是O(n)，使用O(1)的额外空间。
所以编码如下：

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast) {
        fast = fast->next;
        if (fast) fast = fast->next; //避免访问NULL指针的next成员
        slow = slow->next;
        if (fast && fast == slow) return true; //先判断fast是否存在的目的是避免“输入一个只有表头节点的空表，输出true”的情况
    }
    return false;
}

上述算法称为Floyd环路检测，对于长度为n的链表，这个算法使用了O(n)的渐进时间复杂度和O(1)的空间复杂度，这种算法对于链表、有限状态自动机等结构的环路检测效果很好。
如果我们希望求出圈的大小，我们可以在第一次相遇之后多跑一圈，记录下次相遇所用的迭代次数，再加一点小学数学，就可以求出环路的长度。或者也可以使快指针停下来，仅仅通过慢指针即可求出环路的长度。

练习

1 编写一个基于Floyd环路检测的，可以返回环路长度的算法。
2 编写一个基于Floyd环路检测的，可以返回环路起点的算法