链表中环的检测与入口节点的查找：哈希表与快慢指针方法

前言

在数据结构中，链表是一种常见的线性数据结构。链表中的环问题是面试和实际编程中经常遇到的一个问题。本文将先复习哈希表的基本概念，然后介绍两种检测链表中环的方法：哈希表法和快慢指针法，并分析它们的优缺点、原理以及时间和空间复杂度。

哈希表复习

定义：哈希表，又称散列表，是通过哈希函数将键（Key）映射到表中一个位置以便存储和检索数据的数组。

功能：

1. 快速查找：通过哈希函数快速定位数据。
2. 动态扩容：随着元素的增加，哈希表可以动态扩展以保持操作效率。

成员函数：

• insert(K key, V value): 向哈希表中插入一个键值对。
• find(K key): 查找哈希表中是否存在给定的键，并返回相应的值。
• remove(K key): 从哈希表中删除一个键值对。
• size(): 返回哈希表中的元素数量。

检测链表中环的存在及入口节点

哈希表方法

原理：遍历链表，使用哈希表记录访问过的节点。如果再次遇到已记录的节点，则链表存在环。

实现：

ListNode* detectCycle(ListNode* head) {
    std::unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current) {
        if (visited.count(current)) {
            return current; // 找到环的节点
        }
        visited.insert(current);
        current = current->next;
    }
    return nullptr; // 没有环
}

优缺点：

• 优点：实现简单，逻辑直观。
• 缺点：需要额外的存储空间，对于内存敏感的应用可能不是最佳选择。

时间和空间复杂度：

• 时间复杂度：O(n)，n为链表的长度。
• 空间复杂度：O(n)，最坏情况下需要存储整个链表的节点。

  ---

快慢指针方法

原理：使用两个指针，一个快指针（每次移动两个节点）和一个慢指针（每次移动一个节点）。如果存在环，快指针最终会追上慢指针。

实现：

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            break; // 快慢指针相遇，存在环
        }
    }
    if (!fast || !fast->next) {
        return nullptr; // 没有环
    }
    slow = head; // 重置慢指针到头部
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // 快慢指针相遇的节点即为环的入口
}

优缺点：

• 优点：不需要额外的存储空间，空间效率高。
• 缺点：实现相对复杂，需要理解指针的运动规律。

时间和空间复杂度：

• 时间复杂度：O(n)，n为链表的长度。
• 空间复杂度：O(1)，只需要两个指针。

结语

通过本文的介绍，我们了解了两种检测链表中环的方法：哈希表法和快慢指针法。哈希表法简单直观，但需要额外的存储空间；快慢指针法则在空间效率上更胜一筹。在实际应用中，应根据具体需求和环境选择合适的方法。

希望本文能帮助你更好地理解链表环的检测方法。如果你有任何问题或建议，请在评论区告诉我。感谢阅读！

点个关注，和博主做朋友，分享更多知识~