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

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

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

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

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

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：访问节点的下一个节点。

高阶优化：快慢指针的智慧

哪吒元神中突然浮现金色铭文——「三昧真火焚，快慢指针定环踪」。他意识到，可以通过快慢指针的方式，检测链表中是否存在环，并找到环的入口。

哪吒决定使用快慢指针法，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针。如果快指针到达链表末尾，则说明链表无环。