大理州住房和城乡建设部网站免费源码下载网站

大理州住房和城乡建设部网站,免费源码下载网站,用jsp做婚纱网站的流程,网页翻译突然不翻译了快慢指针的两种写法#xff1a;我踩过的坑与总结出的五大典型场景作者#xff1a;一名做梦都想去大厂做后端开发的 Java 工程师 写于#xff1a;2025 年 12 月 26 日 背景#xff1a;最近在刷 LeetCode 和准备系统设计面试时#xff0c;反复遇到快慢指针问题。总被while的…快慢指针的两种写法我踩过的坑与总结出的五大典型场景作者一名做梦都想去大厂做后端开发的 Java 工程师写于2025 年 12 月 26 日背景最近在刷 LeetCode 和准备系统设计面试时反复遇到快慢指针问题。总被while的判断条件搞蒙一、问题起源两种写法到底差在哪快慢指针的核心思想很简单slow每次走 1 步fast每次走 2 步。但循环终止条件却有两种常见写法✅ 写法 A宽松条件while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}✅ 写法 B严格条件while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}初看差别不大但它们决定了slow最终停在哪个“中点”链表长度写法 A宽松写法 B严格1第 1 个第 1 个2第 2 个第 1 个3第 2 个第 2 个4第 3 个第 2 个5第 3 个第 3 个写法 A → 后中点upper middle写法 B → 前中点lower middle这个细微差别在不同算法场景下会产生完全不同的行为。下面是我总结的五大典型应用场景。二、五大典型场景详解场景 1️⃣找链表的中间节点LeetCode 876题目要求如果有两个中间节点返回第二个。输入: [1,2,3,4] 输出: 节点 3即第 3 个✅必须用写法 A宽松条件因为题目明确要“后中点”。写法 A 在偶数长度时让slow停在第n/2 1个节点。 面试陷阱如果用写法 B会返回节点 2直接 Wrong Answer。场景 2️⃣链表归并排序LeetCode 148目标将链表从中间断开递归排序左右两半。关键代码// 找到前中点while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}ListNodemidslow.next;slow.nextnull;// 断开✅必须用写法 B严格条件原因左半部分长度 ≤ 右半部分避免无限递归比如 [1,2] 如果断成 [1,2] 和 null 就炸了。对于偶数长度 n左半段为 n/2右半段为 n/2奇数时左为 (n-1)/2右为 (n1)/2。️ 实战经验我在蚂蚁做日志链表合并时就因用错写法导致栈溢出 OOM。场景 3️⃣判断回文链表LeetCode 234— 反转后半段法策略找到中点 → 反转后半段 → 逐个比较。// Step 1: 找中点后中点while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}// slow 现在是后半段的起点偶数时是第 n/21 个ListNodesecondHalfreverse(slow);✅必须用写法 A宽松条件因为我们要从第二个中间节点开始反转。例如[1,2,2,1]反转从第 3 个节点值为 2开始才能和前半段[1,2]对比。⚠️ 如果用写法 B会把第一个 2 当作后半段起点导致比较错位。场景 4️⃣Floyd 判圈算法LeetCode 141 142目标检测环 找环入口。核心循环while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){/* 有环 */}}✅必须用写法 A宽松条件原因fast每次要走两步所以必须确保fast和fast.next都非空写法 B 会提前退出比如链表只有两个节点且成环1-2-1导致漏判。场景 5️⃣寻找链表倒数第 K 个节点的“中点辅助法”变种应用虽然通常用双指针先走 k 步但在某些分治中点定位的复杂问题中如“链表的随机访问优化”需要精确控制中点位置。例如将链表转换为高度平衡的二叉搜索树LeetCode 109// 构建 BST 需要选“前中点”作为根保证左右子树平衡while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}// slow 是前中点作为 rootTreeNoderootnewTreeNode(slow.val);✅必须用写法 B严格条件因为我们要让左子树节点数 ≤ 右子树符合 AVL 树的平衡要求。若用后中点左子树可能多一个节点破坏“高度平衡”。三、我的记忆口诀为了不再混淆我总结了一句口诀“要后中点用 A宽松要前中点用 B严格。”再加一句安全提醒“涉及fast.next.next的操作必须确保fast.next不为空”所以写法 Afast ! null fast.next ! null→ 安全执行fast.next.next写法 Bfast.next ! null fast.next.next ! null→ 更早退出保slow在前半附速查表场景需求推荐写法代表题目找中间节点返回第二个后中点ALeetCode 876链表归并排序前中点左 ≤ 右BLeetCode 148回文链表反转后半后中点ALeetCode 234Floyd 判圈安全走两步ALeetCode 141/142链表转平衡 BST前中点平衡BLeetCode 109博客完。欢迎留言讨论你遇到的快慢指针坑