C++ 程序 检测链表中的循环

链表是一种常见的数据结构，在算法中被广泛使用，而循环链表是一种特殊的链表，其中最后一个节点的指针指向链表中的第一个节点，也就是说，一个循环链表是一个没有开始或结束的环。

在本文中，我们将介绍如何使用C++编写程序来检测链表中的循环。

什么是循环链表？

一个循环链表由一个或多个节点组成，每个节点包含一个值（或数据元素）以及指向下一个节点的指针，最后一个节点的指针指向第一个节点，从而形成一个环。

以下是一个简单的循环链表的示例代码，其中包含三个节点。每个节点包含一个整数值和指向下一个节点的指针。

struct Node {
    int value;
    Node *next;
};

Node *head = nullptr;
Node *tail = nullptr;

Node *createNode(int val) {
    Node *node = new Node();
    node->value = val;
    node->next = nullptr;
    return node;
}

void appendNode(int val) {
    Node *node = createNode(val);
    if (head == nullptr) {
        head = node;
        tail = node;
        tail->next = head;
    } else {
        tail->next = node;
        tail = node;
        tail->next = head;
    }
}

如何检测循环链表？

现在，我们将学习如何检测循环链表，这是一个有用的技能，因为在某些情况下，我们需要在算法中排除循环链表的干扰。

最常用的方法是使用“快慢指针”技术。假设我们有两个指针，一个每次向前移动一个节点，另一个每次向前移动两个节点。如果链表中不存在循环，则快指针将会越过慢指针并到达链表的末尾。但是，如果链表中存在循环，则快指针将在某个时候遇到慢指针，因为它们都在环中移动。

以下是使用快慢指针检测循环的示例代码：

bool hasCycle(Node *head) {
    if (head == nullptr) {
        return false;
    }
    Node *slow = head;
    Node *fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
        if (slow == fast) {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

完整的程序

下面是一个完整的程序，它使用上述方法检测循环链表。使用此程序，您可以将数字添加到循环链表中，并检查它是否具有循环。

#include <iostream>

using namespace std;

struct Node {
    int value;
    Node *next;
};

Node *head = nullptr;
Node *tail = nullptr;

Node *createNode(int val) {
    Node *node = new Node();
    node->value = val;
    node->next = nullptr;
    return node;
}

void appendNode(int val) {
    Node *node = createNode(val);
    if (head == nullptr) {
        head = node;
        tail = node;
        tail->next = head;
    } else {
        tail->next = node;
        tail = node;
        tail->next = head;
    }
}

bool hasCycle(Node *head) {
    if (head == nullptr) {
        return false;
    }
    Node *slow = head;
    Node *fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
        if (slow == fast) {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

int main() {
    appendNode(1);
    appendNode(2);
    appendNode(3);

    // 检测循环
    if (hasCycle(head)) {
        cout << "链表中存在循环！" << endl;
    } else {
        cout << "链表中不存在循环。" << endl;
    }

    // 将最后一个节点的指针指向第一个节点，形成循环
    tail->next = head;

    // 再次检测循环
    if (hasCycle(head)) {
        cout << "链表中存在循环！" << endl;
    } else {
        cout << "链表中不存在循环。" << endl;
    }

    return 0;
}

输出：

链表中不存在循环。
链表中存在循环！

结论

在本文中，我们介绍了循环链表以及如何使用C++编写程序来检测链表中的循环。通过使用快慢指针技术，我们可以简单而快速地检测循环链表。使用这种技术，您可以更轻松地处理链表，避免循环链表的干扰，并制定更好的算法。