12. 三昧真火焚环劫 - 环形链表检测（快慢指针）

news/2025/2/25 18:10:41

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的环形山脉，山脉中有一条蜿蜒的火龙，它象征着环形链表。山脉的入口处有一块巨大的石碑，上面刻着一行文字：“欲破此山，需以三昧真火之力，焚环劫之链，快慢指针定环踪。”

哪吒定睛一看，石碑上还有一行小字：“链表1 -> 2 -> 3 -> 4 -> 2中存在环，需要检测并找到环的入口。”哪吒心中一动，他知道这是一道关于环形链表检测的难题，需要判断链表中是否存在环，并找到环的入口。

暴力解法：三昧真火的初次尝试

哪吒心想：“要检测链表中是否存在环，我可以逐个节点遍历，用一个集合记录每个节点是否被访问过。”他催动三昧真火，从链表的头节点开始，逐个节点遍历，将每个节点存入集合中。如果发现某个节点已经存在于集合中，说明链表存在环。

cpp">bool hasCycle(ListNode* head) {
   
    unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current) {
   
        if (visited.find(current) != visited.end()) {
   
            return true;  // 发现环
        }
        visited.insert(current);
        current = current->next;
    }
    return false;  // 无环
}

哪吒成功地检测到了链表中的环，但三昧真火的光芒却黯淡了下来。他意识到，这种方法虽然可行，但需要额外的空间来存储访问过的节点，灵力消耗较大。

C++语法点：集合与链表操作

在C++中，集合和链表操作是处理链表问题的常用工具。以下是一些重要特性：

集合：
- unordered_set是一个基于哈希表的集合，用于存储唯一元素。
- 常用方法：
  - insert(value)：插入一个元素。
  - find(value)：查找一个元素是否存在。
链表操作：
- 使用ListNode结构体表示链表节点，包含val（节点值）和next（指向下一个节点的指针）。
- 常用操作：
  - node->next：访问节点的下一个节点。