五个 C++ 中检测链表循环的解决办法

在 C++ 编程中，链表是一种常见的数据结构。然而，链表可能会出现循环的情况，这会导致一些意想不到的错误。下面将介绍五个检测链表循环的有效解决办法。

方法一：快慢指针法

这是一种常见且高效的方法。设置两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。如果链表存在循环，快指针最终会追上慢指针。

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }

    return false;
}

方法二：哈希表法

遍历链表，将每个节点的地址存储在哈希表中。如果遇到已经在哈希表中的地址，说明存在循环。

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> visited;

    while (head) {
        if (visited.count(head)) {
            return true;
        }
        visited.insert(head);
        head = head->next;
    }

    return false;
}

方法三：标记法

为链表节点添加一个额外的标记字段，在遍历过程中标记已访问的节点。再次遇到标记过的节点则表示存在循环。

struct ListNode {
    int val;
    bool visited;
    ListNode* next;
    ListNode(int x) : val(x), visited(false), next(NULL) {}
};

bool hasCycle(ListNode* head) {
    while (head) {
        if (head->visited) {
            return true;
        }
        head->visited = true;
        head = head->next;
    }

    return false;
}

方法四：反转链表法

尝试反转链表，如果反转过程中遇到已经反转过的节点，说明存在循环。但这种方法可能会改变链表的结构。

bool hasCycle(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;

    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;

        if (curr == head) {
            return true;
        }
    }

    return false;
}

方法五：利用节点值

假设节点值可以修改，将遍历过的节点值修改为一个特殊值。再次遇到该特殊值则说明存在循环。

bool hasCycle(ListNode* head) {
    while (head) {
        if (head->val == -1) {
            return true;
        }
        head->val = -1;
        head = head->next;
    }

    return false;
}

以上就是五个在 C++ 中检测链表循环的解决办法，在实际应用中，可以根据具体情况选择合适的方法。