数据结构的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环路检测的,可以返回环路起点的算法


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn