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_setListNode*seen;while(head!nullptr){// 如果当前节点已经被访问过它就是环的入口if(seen.count(head))returnhead;// 记录当前节点seen.insert(head);// 向后移动headhead-next;}// 走到了链表尽头无环returnnullptr;}}; 解法二Floyd 判环算法 (龟兔赛跑进阶)这道题是考察数学推导的经典之作。我们可以用快慢指针分两阶段解决阶段 1判断是否有环并找到相遇点定义快指针fast(每次 2 步) 和慢指针slow(每次 1 步)。如果它们在某处相遇了说明一定有环。阶段 2寻找环的入口 (数学推导)设起点到入口的距离为xxx。设入口到相遇点的距离为yyy。设相遇点到入口的剩余距离为zzz。slow走了xyx yxyfast走了xyn(yz)x y n(y z)xyn(yz)因为fast的速度是slow的两倍2(xy)xyn(yz)2(x y) x y n(y z)2(xy)xyn(yz)化简得到x(n−1)(yz)zx (n - 1)(y z) zx(n−1)(yz)z这个极其漂亮的公式告诉我们起点到环入口的距离xxx刚好等于相遇点走到环入口的距离zzz再加上几圈闲逛。行动指南当两指针相遇后我们把其中一个指针扔回起点另一个留在相遇点。然后两人速度保持一致都每次走 1 步。当他们再次相遇时相交的节点必定是环的入口 C 代码实现 (快慢指针最优解)classSolution{public:ListNode*detectCycle(ListNode*head){if(!head||!head-next)returnnullptr;ListNode*slowhead;ListNode*fasthead;// 阶段 1快慢指针寻找相遇点while(fastfast-next){slowslow-next;fastfast-next-next;// 如果相遇了进入阶段 2if(slowfast){// 将其中一个指针重置到头部ListNode*p1head;ListNode*p2slow;// 两人以相同速度前进相遇点即为环入口while(p1!p2){p1p1-next;p2p2-next;}returnp1;}}returnnullptr;}};