九江市网站建设_网站建设公司_阿里云_seo优化

快慢指针的两种写法：我踩过的坑与总结出的五大典型场景

作者：一名做梦都想去大厂做后端开发的 Java 工程师
写于：2025 年 12 月 26 日
背景：最近在刷 LeetCode 和准备系统设计面试时，反复遇到快慢指针问题。总被while的判断条件搞蒙！

一、问题起源：两种写法到底差在哪？

快慢指针的核心思想很简单：slow每次走 1 步，fast每次走 2 步。但循环终止条件却有两种常见写法：

✅ 写法 A（宽松条件）：

while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}

✅ 写法 B（严格条件）：

while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}

初看差别不大，但它们决定了slow最终停在哪个“中点”：

• 写法 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!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}ListNodemid=slow.next;slow.next=null;// 断开！

✅必须用写法 B（严格条件）
原因：

• 左半部分长度 ≤ 右半部分，避免无限递归（比如 [1,2] 如果断成 [1,2] 和 null 就炸了）。
• 对于偶数长度 n，左半段为 n/2，右半段为 n/2；奇数时左为 (n-1)/2，右为 (n+1)/2。

🛠️ 实战经验：我在蚂蚁做日志链表合并时，就因用错写法导致栈溢出 OOM。

场景 3️⃣：判断回文链表（LeetCode 234）— 反转后半段法

策略：找到中点 → 反转后半段 → 逐个比较。

// Step 1: 找中点（后中点）while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}// slow 现在是后半段的起点（偶数时是第 n/2+1 个）ListNodesecondHalf=reverse(slow);

✅必须用写法 A（宽松条件）
因为我们要从第二个中间节点开始反转。例如[1,2,2,1]，反转从第 3 个节点（值为 2）开始，才能和前半段[1,2]对比。

⚠️ 如果用写法 B，会把第一个 2 当作后半段起点，导致比较错位。

场景 4️⃣：Floyd 判圈算法（LeetCode 141 & 142）

目标：检测环 + 找环入口。

核心循环：

while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){/* 有环 */}}

✅必须用写法 A（宽松条件）
原因：

• fast每次要走两步，所以必须确保fast和fast.next都非空；
• 写法 B 会提前退出（比如链表只有两个节点且成环：1->2->1），导致漏判。

场景 5️⃣：寻找链表倒数第 K 个节点的“中点辅助法”（变种应用）

虽然通常用双指针（先走 k 步），但在某些分治+中点定位的复杂问题中（如“链表的随机访问优化”），需要精确控制中点位置。

例如：将链表转换为高度平衡的二叉搜索树（LeetCode 109）

// 构建 BST 需要选“前中点”作为根，保证左右子树平衡while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}// slow 是前中点，作为 rootTreeNoderoot=newTreeNode(slow.val);

✅必须用写法 B（严格条件）
因为我们要让左子树节点数 ≤ 右子树，符合 AVL 树的平衡要求。若用后中点，左子树可能多一个节点，破坏“高度平衡”。

三、我的记忆口诀

为了不再混淆，我总结了一句口诀：

“要后中点，用 A（宽松）；要前中点，用 B（严格）。”

再加一句安全提醒：

“涉及fast.next.next的操作，必须确保fast.next不为空！”

所以：

• 写法 A：fast != null && fast.next != null→ 安全执行fast.next.next
• 写法 B：fast.next != null && fast.next.next != null→ 更早退出，保slow在前半

附：速查表

博客完。欢迎留言讨论你遇到的快慢指针坑！