wordpress站安装百度商桥网站维护的内容

wordpress站安装百度商桥,网站维护的内容,建筑图纸怎么学看图,临沂河东区建设局网站LCR 022. 环形链表 II#xff1a;返回链表开始入环的第一个节点 #x1f680; 在链表类算法中#xff0c;环形链表相关题目绝对是面试高频考点#xff01;从基础的“判断链表是否有环”#xff0c;到进阶的“找到入环第一个节点”#xff0c;层层递进的考察方式能很好地…LCR 022. 环形链表 II返回链表开始入环的第一个节点 在链表类算法中环形链表相关题目绝对是面试高频考点从基础的“判断链表是否有环”到进阶的“找到入环第一个节点”层层递进的考察方式能很好地检验我们对链表结构和双指针技巧的理解。今天就来深度拆解 LCR 022. 环形链表 II带你从原理到代码彻底搞懂这道经典题一、回顾昨日算法题环形链表判断链表是否有环 的核心逻辑 在解决“找入环节点”之前我们先回顾它的基础题——“判断链表是否有环”。这道题的核心解法是快慢指针法思路特别形象定义两个指针fast快指针和slow慢指针同时从链表头head出发fast每次走 2 步slow每次走 1 步就像两个人在环形跑道上跑步速度不同如果链表没有环fast会先跑到链表末尾遇到null此时直接返回无环如果链表有环slow进入环后就会一直在环内循环而fast会在环内追上slow相当于套圈此时就能确定链表有环。代码亮个相function hasCycle(head) { let slow head; let fast head; while(fast fast.next) { // 快指针先到尾部 slow slow.next; fast fast.next.next; if(slow fast) { // 同一块内存 return true; } } return false; }如果看不懂上面代码可以先看看我掘金昨天关于快慢指针解决环形链表的文章哨兵节点与快慢指针解决链表算法难题哨兵节点统一链表操作逻辑简化边界处理快慢指针高效解决环检测与倒数第N个节点等问题。 - 掘金这个基础逻辑是解决 LCR 022 的前提而 LCR 022 不仅要求判断是否有环还需要找到入环的第一个节点难度升级啦二、核心突破如何找到入环第一个节点 1. 问题衔接先判环再找入口解决 LCR 022 的第一步和基础题完全一致——用快慢指针判断链表是否有环。如果没有环直接返回null如果有环就进入关键步骤通过指针路程的数学关系推导出入环节点的位置。2. 关键推导快慢指针的路程关联这一步是核心先明确变量定义设X链表头head到入环第一个节点的距离节点数设C环形部分的长度环的节点总数设Y入环第一个节点到快慢指针相遇点的距离节点数。接下来分析快慢指针的路程从出发到相遇由于fast一定比slow先入环slow入环时fast可能已经绕环走了一圈、两圈、三圈…最好情况slow一入环即与fast相遇。最坏情况当slow入环时与fast的距离刚好是环的长度此时两个指针每移动一步之间的距离就缩小一步不会出现内次刚好套圈的情况因此在慢指针走完一圈之前快指针肯定可以追上慢指针。慢指针slow速度是 1 步/次路程 X Y——先从 head 走到入环口X 步再沿环走 Y 步到达相遇点未绕环快指针fast速度是 2 步/次且比slow先入环相遇时已绕环n圈n ≥ 1追上至少绕 1 圈路程 X nC Y——先到入环口X 步绕环 n 圈nC 步再走 Y 步到相遇点。示意图因fast路程是slow的 2 倍速度 2 倍且同时出发列等式2 × (X Y) X nC Y化简后核心结论X nC - Y这个结论的意义是链表头到入环口的距离 X等于相遇点绕环 n 圈后再倒回 Y 步的距离。当n1时最易理解fast 绕环 1 圈追上 slow公式简化为X C - Y即“head 到入环口的距离 相遇点到入环口的环内剩余距离”。因此只要让一个指针从head出发另一个指针从相遇点出发两者以相同速度1 步/次前进最终一定会在入环口相遇——因为前者走 X 步到入环口后者走 X nC - Y 步绕 n 圈后再走 C-Y 步也到入环口。3. 代码实现与逐行解析基于上面的推导代码逻辑清晰结合给出的代码逐行拆解/** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} head * return {ListNode} */ var detectCycle function(head) { // 1. 初始化快慢指针都从 head 出发 let fast head; let slow head; // 2. 快慢指针移动判断是否有环 while(fast ! null fast.next ! null) { fast fast.next.next; // 快指针走 2 步 slow slow.next; // 慢指针走 1 步 if(fast slow) { // 相遇说明有环跳出循环 break; } } // 3. 无环情况fast 走到末尾null 或倒数第一个节点 if(fast null || fast.next null) { return null; } // 4. 找入环口slow 回 head两者同速前进 slow head; while(slow ! fast) { slow slow.next; fast fast.next; } // 5. 相遇点就是入环口 return slow; };代码逻辑分 5 步每一步都与推导对应第一步初始化指针保证起点一致第二步通过快慢指针移动判环fast先到末尾则无环第三步处理无环场景直接返回null第四步是核心slow回到headfast留在相遇点两者同速走第五步相遇时指针指向的就是入环第一个节点返回即可三、面试官可能会问的灵魂拷问 这道题的代码不算复杂但面试官更看重你对原理的理解这些问题一定要提前准备为什么快慢指针一定会相遇会不会永远追不上不会因为fast速度比slow快 1 步/次相当于两者之间的距离每次缩小 1 步。哪怕slow入环时fast刚好在它身后距离为C最多C步后fast一定会追上slow且slow此时还没绕环 1 圈修正此前“内次刚好套圈”为笔误不会出现每次都刚好错开的情况。除了双指针还有其他解法吗两者对比如何有用哈希表Set存储遍历过的节点每次遍历到新节点时判断是否已在哈希表中如果是该节点就是入环口如果不是加入哈希表。 对比哈希表解法时间复杂度O(n)但空间复杂度O(n)需要存储节点双指针解法空间复杂度O(1)仅用两个指针是更优的解法也是面试中更常考察的思路。n公式推导中 可以取任意正整数为什么最终结果不受影响因为nC是环的整数圈fast从相遇点出发走X nC - Y步时会先绕n圈回到相遇点附近再走C - Y步到达入环口——这和绕 0 圈直接走C - Y步的终点完全一致。所以不管n是多少两个指针最终都会在入环口相遇。四、结语 ✨LCR 022. 环形链表 II 是双指针技巧的经典应用核心在于“判环 路程推导”两步走。这道题的魅力在于没有复杂的语法却需要清晰的逻辑思维和数学推导能力这也是它成为面试高频题的原因。学习这道题时建议大家先手动模拟简单案例跟着指针的移动轨迹理解相遇点和入环口的关系再结合公式推导加深记忆。记住代码只是逻辑的载体理解背后的原理才能真正掌握这类题本题原题链接https://leetcode.cn/problems/c32eOV/