济南网站app开发的京紫元年网站建设

济南网站app开发的,京紫元年网站建设,NextApp wordpress,pc网站制作APP这个问题是典型的**“双指针”**应用场景。它的巧妙之处在于#xff1a;不需要先测量整个链表的长度#xff0c;通过两个指针的“距离差”#xff0c;只需一次遍历就能找到倒数第 NNN 个节点。1. 核心思路#xff1a;快慢指针#xff08;等距离滑动#xff09; 要删除倒数…这个问题是典型的**“双指针”**应用场景。它的巧妙之处在于不需要先测量整个链表的长度通过两个指针的“距离差”只需一次遍历就能找到倒数第NNN个节点。1. 核心思路快慢指针等距离滑动要删除倒数第NNN个节点我们需要找到它的前驱节点即倒数第N1N1N1个节点。设置虚拟头节点 (dummy)依然是老规矩为了处理删除“第一个节点”的情况先创建一个dummy指向head。快指针 (fast) 先走让fast先向后移动N1N1N1步。此时fast和慢指针slow此时在dummy之间隔了NNN个节点。同速前进让fast和slow同时向后移动。当fast到达链表末尾None时slow刚好停在倒数第N1N1N1个节点上。“跨越”删除执行slow.next slow.next.next。原理直观图示假设链表长度为LLL找倒数第NNN个就是找正数第L−N1L-N1L−N1个。让fast先走NNN步剩下还要走L−NL-NL−N步到头。此时slow从头开始走L−NL-NL−N步正好停在倒数第NNN个的前面。2. 代码实现 (Python)classSolution:defremoveNthFromEnd(self,head:ListNode,n:int)-ListNode:# 1. 哨兵节点处理删除头节点的情况dummyListNode(0,head)fastdummy slowdummy# 2. 快指针先走 n 1 步# 这样快慢指针之间就会间隔 n 个节点for_inrange(n1):fastfast.next# 3. 快慢指针同时移动直到快指针指向空whilefast:fastfast.nextslowslow.next# 4. 此时 slow 停在倒数第 n 个节点的前驱节点上# 直接跳过倒数第 n 个节点slow.nextslow.next.nextreturndummy.next3. 为什么是走n 1步这是一个容易出错的细节。我们要删除的是“倒数第NNN个”。在链表里删除一个节点必须找到它的前一个。如果你让fast先走NNN步当fast走到None时slow会停在“倒数第NNN个”上。这时候你没法删除它因为你拿不到它的前驱节点。所以我们让fast多走一步N1N1N1步这样slow就会正好落在“倒数第NNN个”的左边那位也就是倒数第N1个位置这样slow的next就可以指向slow.next.next4. 复杂度分析时间复杂度O(L)O(L)O(L)其中LLL是链表长度。我们只对链表进行了一次遍历。空间复杂度O(1)O(1)O(1)。只额外使用了两个指针。总结这道题展示了双指针的一种常用技巧——“固定距离滑窗”。通过让一个指针先跑制造出一种“空间换时间”的效果避免了“先数一遍长度再跑第二遍”的尴尬。这个问题紧接着我们刚才讨论的“快慢指针”思路是该技巧的又一经典应用。1. 核心技巧快慢指针速度差法要找到并删除中间节点我们可以利用“快指针的速度是慢指针的两倍”这一特性慢指针 (slow)每次走1步。快指针 (fast)每次走2步。当快指针走到链表末尾时慢指针刚好就在中点附近。寻找“前驱节点”的艺术和删除倒数第NNN个节点一样删除中点必须拿到中点的前一个节点。如果链表长度n4n 4n4中点是下标222。我们需要停在下标111。如果链表长度n5n 5n5中点是下标222。我们需要停在下标111。为了方便处理头节点比如只有一个节点的情况我们依然请出dummy节点。2. 代码实现 (Python)classSolution:defdeleteMiddle(self,head:Optional[ListNode])-Optional[ListNode]:# 1. 特判如果只有一个节点删除后为空ifnotheadornothead.next:returnNone# 2. 设置虚拟头节点pre 最终要停在中点的前一个dummyListNode(0,head)slowdummy fasthead# 让 fast 从 head 开始slow 从 dummy 开始# 3. 快慢指针跑起来# 当 fast 走完 2 步slow 走 1 步whilefastandfast.next:fastfast.next.nextslowslow.next# 4. 此时 slow 恰好停在中点的前驱位置# 比如 1-2-3-4-5slow 会停在 2中点是 3slow.nextslow.next.nextreturndummy.next3. 为什么这样跑能精准定位让我们手动模拟一下场景 A长度n4n 4n4(偶数)链表dummy - 1 - 2 - 3 - 4 - None初始slow在dummy,fast在1。第一轮fast移到3,slow移到1。第二轮fast移到None,slow移到2。循环结束slow停在2。中点下标⌊4/2⌋2\lfloor 4/2 \rfloor 2⌊4/2⌋2即节点3。slow.next正好指向节点3。定位正确场景 B长度n5n 5n5(奇数)链表dummy - 1 - 2 - 3 - 4 - 5 - None初始slow在dummy,fast在1。第一轮fast移到3,slow移到1。第二轮fast移到5,slow移到2。此时fast.next为空循环结束slow停在2。中点下标⌊5/2⌋2\lfloor 5/2 \rfloor 2⌊5/2⌋2即节点3。slow.next正好指向节点3。定位正确4. 复杂度分析时间复杂度O(N/2)O(N/2)O(N/2)即O(N)O(N)O(N)。我们只遍历了半个链表长度快指针到头即止。空间复杂度O(1)O(1)O(1)。只用了两个指针。总结链表的题目其实很有规律怕断掉操作前先存next。怕头变先建dummy。找位置固定距离用“滑窗双指针”倒数第NNN个。比例距离用“速度差双指针”中点。虽然它们都叫“双指针”但**“滑窗”和“速度差”**在逻辑设计和解决的问题类型上有着本质的区别。我们可以通过下面这个对比来清晰地理解1. 固定距离滑窗双指针 (Sliding Window)核心逻辑两个指针的步速相同每次都走 1 步但出发时间不同。操作方法先让fast走NNN步然后slow才开始从起点走。物理意义两指针之间维持一个恒定的刻度线窗口。解决的问题寻找相对于末尾固定位置的节点。例子倒数第 5 个。无论链表多长我只要保证我身后的“影子”跟我差 5 个身位当我撞到终点墙壁时影子就在倒数第 5 个。2. 比例距离速度差双指针 (Fast Slow Pointers)核心逻辑两个指针的出发时间相同但步速不同通常是 2:1。操作方法fast每次走 2 步slow每次走 1 步。物理意义两指针之间维持一个恒定的比例关系。解决的问题寻找相对于全长比例位置的节点。例子中点1/2 处。因为Vfast2×VslowV_{fast} 2 \times V_{slow}Vfast​2×Vslow​所以在相同时间内slow走过的路程永远是fast的一半。当fast跑完全程100%时slow自然就在中点50%。3. 直观对比表特性滑窗双指针 (Fixed Gap)速度差双指针 (Ratio Gap)步频一样 (1:1)不一样 (通常 2:1)间距固定长度(Gap N)动态增长(Gap 随步数增加)关键参数NNN(具体的个数)1/21/21/2或1/31/31/3(比例)典型应用倒数第NNN个节点寻找中点、判断是否有环4. 为什么会有这种区分这取决于你对**“终点”**的利用方式滑窗利用的是“终点”作为一个锚点。因为我们不知道链表有多长但我们知道“终点”在哪里所以通过一个固定长度的“标尺”往回倒推。速度差利用的是“终点”作为一个计时器。我们用快指针跑完全程的时间来换取慢指针刚好走到比例位置的结果。进阶思考判断“环”在LeetCode 141. 环形链表中我们使用速度差双指针。为什么不用滑窗因为在环里没有“倒数第几个”的概念没有尽头但速度差会让快指针在环里“多跑一圈”最终追上慢指针套圈就像操场长跑一样。这就引出了链表最神奇的一个算法弗洛伊德判圈算法。快慢指针是怎么在环里“相遇”的吗这个问题是**“速度差双指针”**最经典的应用场景通常被称为“龟兔赛跑算法”Floyd’s Cycle-Finding Algorithm。1. 核心原理套圈想象一下在一个环形跑道上比赛兔子快指针fast每次跑 2 个台阶。乌龟慢指针slow每次跑 1 个台阶。如果跑道是直的兔子会先到达终点乌龟永远追不上兔子。如果跑道有环兔子进入环后会开始转圈。由于兔子比乌龟快它最终一定会从后面**“套圈”**乌龟两人必然会在某个点相遇。2. 代码实现 (Python)classSolution:defhasCycle(self,head:Optional[ListNode])-bool:# 如果链表为空或只有一个节点且无环直接返回 falseifnotheadornothead.next:returnFalseslowhead fasthead# 只要快指针没跑出边界即没遇到 Nonewhilefastandfast.next:slowslow.next# 走 1 步fastfast.next.next# 走 2 步# 如果两个指针相遇了说明有环ifslowfast:returnTrue# 如果跳出了循环说明快指针走到了终点没有环returnFalse3. 深度思考为什么快指针每次走 2 步走 3 步、4 步行吗2 步是最稳妥的当快指针进入环并开始追赶慢指针时它们之间的相对速度是2−112 - 1 12−11。这意味着它们之间的距离每走一步就缩短 1最终距离一定会变成 0相遇不会跳过去。如果走 3 步相对速度是 2。如果它们之间的距离是奇数快指针可能会在某一跨度直接“跳过”慢指针导致它们需要多跑好几圈才能相遇甚至在某些离散数学的模型下永远不相遇。为什么不需要dummy节点因为这道题不涉及修改链表结构不删除也不反转我们只是在链表上“跑步”。即使从头节点开始就有环slow fast的逻辑依然成立所以不需要哨兵节点。4. 复杂度分析时间复杂度O(N)O(N)O(N)。如果没有环快指针走N/2N/2N/2步到头。如果有环快指针进入环后最多在慢指针转完一圈之前就能追上它。空间复杂度O(1)O(1)O(1)。我们只用了两个指针没有使用额外的哈希表。