当前位置：首页 > news >正文

【Hot 100 刷题计划】 LeetCode 142. 环形链表 II | C++ 哈希表直觉解法

news 2026/7/6 22:54:27

LeetCode 142. 环形链表 II

📌 题目描述

题目级别：中等

给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
不允许修改链表。

示例 1:
输入：head = [3,2,0,-4],pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

💡 解法一：哈希表备忘录

想要找到“环的入口”，最直接的想法就是“留下脚印”。
我们在遍历链表的过程中，把路过的每一个节点的指针都记在哈希表（HashSet）里。
不断往前走，每走到一个新节点，都先去查一下表：

如果表中不存在，就把当前节点记录下来，继续往下走。
如果走到某个节点，发现它已经在哈希表里了！那么毫无疑问，这个节点就是我们绕了一圈后第一次重新踏足的地方，它就是环的入口节点！
如果一路走到nullptr，说明这是一条直线，直接返回null。

💻 C++ 代码实现 (哈希表法)

classSolution{public:ListNode*detectCycle(ListNode*head){// 使用 unordered_set 记录已经访问过的节点unordered_set<ListNode*>seen;while(head!=nullptr){// 如果当前节点已经被访问过，它就是环的入口if(seen.count(head))returnhead;// 记录当前节点seen.insert(head);// 向后移动head=head->next;}// 走到了链表尽头，无环returnnullptr;}};

💡 解法二：Floyd 判环算法 (龟兔赛跑进阶)

这道题是考察数学推导的经典之作。我们可以用快慢指针分两阶段解决：

阶段 1：判断是否有环，并找到相遇点
定义快指针fast(每次 2 步) 和慢指针slow(每次 1 步)。如果它们在某处相遇了，说明一定有环。

阶段 2：寻找环的入口 (数学推导)
设起点到入口的距离为xxx。
设入口到相遇点的距离为yyy。
设相遇点到入口的剩余距离为zzz。

slow走了x+yx + yx+y
fast走了x+y+n(y+z)x + y + n(y + z)x+y+n(y+z)
因为fast的速度是slow的两倍：
2(x+y)=x+y+n(y+z)2(x + y) = x + y + n(y + z)2(x+y)=x+y+n(y+z)
化简得到：
x=(n−1)(y+z)+zx = (n - 1)(y + z) + zx=(n−1)(y+z)+z
这个极其漂亮的公式告诉我们：起点到环入口的距离xxx，刚好等于相遇点走到环入口的距离zzz（再加上几圈闲逛）。

行动指南：
当两指针相遇后，我们把其中一个指针扔回起点，另一个留在相遇点。然后两人速度保持一致（都每次走 1 步）。当他们再次相遇时，相交的节点必定是环的入口！

💻 C++ 代码实现 (快慢指针最优解)

classSolution{public:ListNode*detectCycle(ListNode*head){if(!head||!head->next)returnnullptr;ListNode*slow=head;ListNode*fast=head;// 阶段 1：快慢指针寻找相遇点while(fast&&fast->next){slow=slow->next;fast=fast->next->next;// 如果相遇了，进入阶段 2if(slow==fast){// 将其中一个指针重置到头部ListNode*p1=head;ListNode*p2=slow;// 两人以相同速度前进，相遇点即为环入口while(p1!=p2){p1=p1->next;p2=p2->next;}returnp1;}}returnnullptr;}};