双指针

副标题 / 摘要 这题的核心不是“删除节点”，而是“如何在单链表里定位倒数第 N 个节点的前驱”。本文从朴素思路推导到一趟双指针解法，用 ACERS 结构讲透正确性、边界处理与工程迁移。 预计阅读时长：12~15 分钟 适用场景标签：链表基础、双指针、面试高频 SEO 关键词：LeetCode 19, Remove Nth Node From End of List, 删除链表倒数第 N 个结点, 快慢指针, 哨兵节点 元描述（Meta Description）：删除链表倒数第 N 个结点的完整 ACERS 解析：从暴力到一趟双指针，含复杂度、常见坑、工程示例与 Python/C/C++/Go/Rust/JS 代码。 目标读者 刚开始刷链表题，想建立稳定解题模板的同学 知道快慢指针，但容易在边界条件上出错的开发者 希望把“题解能力”迁移到工程链式数据处理场景的后端/系统工程师 背景 / 动机 “删除倒数第 N 个节点”是链表题里的经典中档题，常见难点不在删除本身，而在： 单链表不能回退，无法直接从尾部向前数； 可能删除头节点，导致返回值处理复杂； 一旦 next 指针处理失误，容易断链或越界。 掌握它的价值在于： 你会形成一套可复用的“哨兵节点 + 双指针间距控制”模板，这对后续链表题（分组翻转、分割、合并）都很关键。 核心概念 单链表（Singly Linked List）：每个节点只有 next 指针，只能向后遍历。 哨兵节点（dummy）：在头结点前增加一个虚拟节点，统一“删除头节点”和“删除中间节点”的处理逻辑。 快慢指针固定间距：先让 fast 领先 slow 共 n 步，再同步前进；当 fast 到达末尾时，slow 正好停在目标节点前驱。 A — Algorithm（题目与算法） 题目重述 给你一个链表，删除链表的倒数第 n 个结点，并返回链表的头结点。 ...

副标题 / 摘要 LeetCode 25 是“整链反转（206）”与“区间反转（92）”的组合升级：你要按组切分、组内反转、组间拼接，并正确处理不足 k 的尾组。本文用 ACERS 模板给出工程可复用解法。 预计阅读时长：14~18 分钟 标签：Hot100、链表、分组反转、哑节点 SEO 关键词：Reverse Nodes in k-Group, K 个一组翻转链表, 分组反转, LeetCode 25, Hot100 元描述：K 组链表原地反转模板：分组扫描 + 区间反转 + 安全拼接，含复杂度分析、常见坑与多语言代码。 目标读者 已掌握 206 / 92，希望攻克“多区间连续反转”的 Hot100 学习者 链表题常在边界和拼接步骤出错的中级开发者 需要构建稳定“链表分段处理”模板的工程师 背景 / 动机 在工程里，链式结构的批处理并不少见： 任务链按固定批次重排执行 流水线节点按批回滚或重放 数据清洗链表按批次做原地变换 这类场景的核心诉求是： 组内变换（例如反转） 组间保持顺序 尾部残组按规则保留（不足 k 不反转） LeetCode 25 正是这个能力的典型建模。 核心概念 哑节点（dummy）：统一处理头节点参与反转的场景 组前驱（groupPrev）：指向当前组前一个节点 组尾探针（kth）：从 groupPrev 出发找第 k 个节点，判断是否够一组 组后继（groupNext）：当前组反转后要接回的后半链头 组内原地反转：只反转 [groupStart, kth] 区间 A — Algorithm（题目与算法） 题目还原 给你链表头节点 head 和整数 k，每 k 个节点一组进行翻转，返回修改后的链表。 若剩余节点数不足 k，则保持原顺序不变。 要求只能改节点指针，不允许只改节点值。 ...

副标题 / 摘要 这题的价值在于把“判环”升级为“定位入环点”。最稳的工程化模板是 Floyd：先用快慢指针在环内相遇，再让一个指针回到头结点同步走，下一次相遇的位置就是入环点。全程不修改链表，O(n) 时间、O(1) 额外空间。 预计阅读时长：12~16 分钟 标签：Hot100、链表、快慢指针、Floyd SEO 关键词：环形链表 II, 入环点, Floyd 判圈, 快慢指针, O(1) 空间, LeetCode 142 元描述：Floyd 快慢指针判环并定位入环点：相遇后从头与相遇点同步前进，返回入环的第一个节点；O(n)/O(1)，不允许修改链表。 目标读者 刷 Hot100，想把“判环/入环点定位”模板一次性吃透的学习者 需要写健壮链式结构遍历（避免死循环）并能定位故障节点的工程师 面试里被问到“为什么 reset 之后会在入环点相遇”的同学 背景 / 动机 链表一旦出现环，任何“遍历到 null 为止”的代码都可能进入死循环。 工程里造成环的原因很多：指针写错、复用节点、数据结构被破坏、并发读写导致 next 异常等。 因此除了“有没有环”，更重要的是： 环从哪里开始？（入环点） 找到入环点可以帮助你定位哪一个节点的 next 被错误地连回去了，这比单纯返回 true/false 更有诊断价值。 题目还明确要求：不允许修改链表，所以不能用“打标记/改值/断链”等手段。 核心概念 概念 含义 作用 环 沿 next 走能再次回到某节点 会导致遍历死循环 入环点 从头结点沿 next 首次进入环的那个节点 题目要求返回它 Floyd 判圈 快慢指针：slow 每次 1 步，fast 每次 2 步 O(1) 空间判环 相遇点 slow 与 fast 在环内第一次相遇的位置 用来进一步定位入环点 引用相等 判断是否为同一节点对象/地址 不能用值相等代替 A — Algorithm（题目与算法） 题目还原 给定链表头节点 head，返回链表开始入环的第一个节点；如果链表无环，返回 null。 ...

副标题 / 摘要 这是链表版的“归并排序合并步骤”：两条升序链表像两根排好队的队伍，比较头部把更小的节点接到结果尾部即可。本文用 ACERS 结构把哨兵节点迭代写法讲透，并给出递归对照与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、链表、归并、双指针 SEO 关键词：Hot100, Merge Two Sorted Lists, 合并两个有序链表, 归并, 哨兵节点, LeetCode 21 元描述：哨兵节点 + 双指针 O(m+n) 合并两个升序链表，附递归对比、工程迁移与多语言实现。 目标读者 正在刷 Hot100 / 准备面试的同学 写链表题经常丢头/断链、希望建立稳定模板的中级开发者 需要在 C/C++/Go/Rust 等语言里熟练做“拼接式合并”的工程师 背景 / 动机 “合并两个有序链表”看上去是简单题，但它非常像工程里的真实任务： 合并两路已排序的数据流（日志、事件、时间线） 合并两份排序好的列表（缓存片段、分片结果、分页结果） 在 O(1) 额外空间下复用节点，避免额外分配与拷贝 更重要的是：它是很多题的前置技能（如合并 k 个链表、排序链表、分治归并）。 把这个模板写熟，你后续的链表题会明显更顺。 核心概念 升序链表：沿 next 方向节点值非递减 拼接式合并（splicing）：不创建新节点（除哨兵节点外），只重连 next 指针把节点接到结果链表 哨兵节点（dummy/sentinel）：用一个虚拟头简化“结果链表头是谁”的特判 尾指针（tail）：始终指向结果链表的最后一个节点，方便 O(1) 追加 A — Algorithm（题目与算法） 题目还原 给你两个升序链表 list1 和 list2 的头节点， 请将它们合并为一个新的 升序 链表并返回。 新链表是通过 拼接 给定的两个链表的所有节点组成的。 ...

副标题 / 摘要 判断链表是否有环，本质是“指针追及问题”。本文用 ACERS 结构讲透 Floyd 快慢指针判环：为什么一定能相遇、如何避免空指针、以及在工程里如何用同一思想识别循环引用/路由环路。 预计阅读时长：10~12 分钟 标签：Hot100、链表、快慢指针 SEO 关键词：Hot100, Linked List Cycle, 环形链表, 判环, Floyd, 快慢指针, LeetCode 141 元描述：Floyd 快慢指针 O(n)/O(1) 判断单链表是否有环，附替代方案对比、易错点与多语言实现。 目标读者 正在刷 Hot100 / 准备面试的同学 想把“链表双指针”沉淀成稳定模板的中级开发者 在工程里需要识别循环引用、链式结构异常的同学（C/C++/Go/Rust/JS 皆适用） 背景 / 动机 链表出现环在工程里并不罕见： 例如手写内存池的 free list、对象引用链、状态机/任务编排的 next 指针、配置链路的“下一跳”等。 一旦出现环： 遍历会进入死循环（CPU 占用飙高，日志刷爆） 资源释放/回收会卡死（例如释放链表节点时无限循环） 监控定位困难（看起来像“偶发卡死”，本质是结构性错误） 因此你需要一个不依赖额外内存、可在线检测的判环方法：Floyd 快慢指针就是这类问题的标准答案。 核心概念 环（Cycle）：从某个节点开始，沿 next 指针走若干步能回到自己 pos（评测用）：题目描述里的 pos 仅用于评测系统构造数据；你的函数不会收到 pos 参数 快慢指针（Floyd）：慢指针每次走 1 步，快指针每次走 2 步；若存在环，二者必定在环内相遇 指针相等 vs 值相等：判环必须比较“节点身份”（引用/地址），不能只比 val（值可能重复） A — Algorithm（题目与算法） 题目还原 给你一个链表的头节点 head，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 ...

副标题 / 摘要 相交链表的关键不是比较值，而是比较“节点引用/地址”。本文用 ACERS 结构把朴素哈希解法、长度对齐解法与最常用的“双指针换头”模板讲清楚，并给出多语言可运行实现（不修改链表、无环前提）。 预计阅读时长：10~14 分钟 标签：Hot100、链表、双指针 SEO 关键词：相交链表, 双指针换头, O(1) 空间, LeetCode 160, Intersection of Two Linked Lists 元描述：双指针分别走完 A 与 B 后交换起点，保证在 m+n 步内相遇于交点或同时到达 null；O(m+n)/O(1) 且不修改链表结构。 目标读者 刷 Hot100，希望把链表双指针模板一次性吃透的学习者 经常把“节点值相等”误当作“节点相同”的初中级开发者 需要在工程里处理共享链式结构（共享后缀/共享节点）的工程师 背景 / 动机 这题看似简单，但它强迫你分清三个概念： 相交是“共享同一个节点对象/地址”，不是值相等 不能破坏结构（不能改 next、不能打标记） 还要高效：把 O(mn) 降到线性 最经典的工程化答案是“双指针换头”： 它不用额外集合、不需要先算长度，只靠指针走路就能在 m+n 步内完成同步。 核心概念 概念 含义 备注 节点相同 两个指针指向同一块内存/同一个对象 语言里通常是引用相等/指针相等 共享后缀 两条链表在某个节点开始共享接下来的所有节点 交点之后完全一致 双指针换头 指针走到链尾后跳到另一条链表的头 让两指针走过相同总路程 无环保证 题目保证整个结构无环 否则需要额外环检测处理 A — Algorithm（题目与算法） 题目还原 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。 如果两个链表不存在相交节点，返回 null。 ...

副标题 / 摘要 轮转数组是典型的数组变换题：把数组整体向右移动 k 位。本文用 ACERS 拆解“三次反转”的核心思路，并给出工程场景迁移与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、数组、旋转 SEO 关键词：Rotate Array, 轮转数组, 数组旋转, 反转, O(n) 元描述：三次反转法解决轮转数组，含复杂度对比、工程场景与多语言代码。 目标读者 正在刷 Hot100 的学习者 想掌握“数组原地变换”模板的中级开发者 需要处理时间序列对齐、轮值偏移的工程师 背景 / 动机 轮转数组在工程中非常常见： 轮值排班、时间序列对齐、环形缓冲区、前端轮播等都可以抽象为“整体右移 k 位”。 如果用逐步移动会变成 O(nk)，在数据量稍大时就不可用，因此需要更高效的原地方案。 核心概念 轮转（rotate）：把数组向右移动 k 位，后 k 个元素移到最前 k 取模：k %= n，避免 k 超过数组长度 反转（reverse）：用双指针交换来原地反转区间 原地（in-place）：在原数组上操作，额外空间 O(1) A — Algorithm（题目与算法） 题目还原 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 输入输出 名称 类型 描述 nums int[] 整数数组 k int 向右轮转步数 返回 int[] 轮转后的数组 示例 1（官方） 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 示例 2（官方） 输入: nums = [-1,-100,3,99], k = 2 输出: [3,99,-1,-100] C — Concepts（核心思想） 关键思路：三次反转 反转整个数组 反转前 k 个 反转后 n-k 个 反转后的位置关系刚好等价于右移 k 位。 ...

副标题 / 摘要 接雨水是最经典的“区间高度约束”题。本文按 ACERS 模板讲清双指针思路、关键公式与工程迁移，并提供多语言可运行实现。 预计阅读时长：12~15 分钟 标签：Hot100、双指针、数组 SEO 关键词：Trapping Rain Water, 接雨水, 双指针, 前后最大值, O(n) 元描述：双指针 O(n) 求接雨水总量，含工程场景、复杂度分析与多语言代码。 目标读者 正在刷 Hot100 的学习者 需要掌握“左右边界约束”模板的中级开发者 处理地形/容量/水位等区间分析的工程师 背景 / 动机 接雨水问题本质是“每个位置能盛多少水”，与工程中的容量评估、缓冲区盈余、资源占用上限等模型高度相似。 朴素做法每个位置都向两侧找最高，复杂度 O(n^2)。 双指针与前后最大值可以把复杂度降到 O(n)。 核心概念 局部水位：water[i] = min(maxLeft[i], maxRight[i]) - height[i] 左右边界：当前位置两侧的最高柱子决定水位上限 双指针：用左/右指针同步维护左右最大值 A — Algorithm（题目与算法） 题目还原 给定 n 个非负整数表示每个宽度为 1 的柱子的高度，计算按此排列的柱子能接多少雨水。 输入输出 名称 类型 描述 height int[] 柱子高度数组 返回 int 能接住的雨水总量 示例 1（官方） height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出 = 6 示例 2（官方） height = [4,2,0,3,2,5] 输出 = 9 C — Concepts（核心思想） 关键公式 对任意位置 i： ...

副标题 / 摘要 固定间距 1 检测是典型的“事件间距校验”模型。本文按 ACERS 结构拆解题意、原理与工程迁移，并给出多语言可运行实现。 预计阅读时长：10~12 分钟 标签：数组、双指针、事件间距 SEO 关键词：固定间距 1 检测, 事件间距, LeetCode 1437, O(n) 元描述：一次扫描判断所有 1 是否至少相隔 k 个位置，含工程场景、复杂度对比与多语言代码。 目标读者 刷 LeetCode 并希望沉淀“模板题”的学习者 做监控/风控/行为分析的工程师 需要判断事件间隔是否合规的系统开发者 背景 / 动机 许多系统都有“事件不能过密”的约束：例如登录失败、报警事件、敏感操作、API 调用等。 这类问题的本质是 “事件间距是否满足阈值”，与该题完全等价。 如果能用 O(n) 一次扫描完成校验，就能直接迁移到实时系统。 核心概念 事件间距：两个事件之间至少有 k 个“空位” 在线校验：只记住上一次事件的位置即可 边界处理：初始化 last = -k-1，消除首个事件特判 A — Algorithm（题目与算法） 题目还原 给定整数数组 nums 与整数 k，若任意两个 1 之间至少有 k 个 0（等价于两次 1 的索引差 > k），返回 true，否则返回 false。 输入输出 名称 类型 描述 nums int[] 仅包含 0/1 的数组 k int 需要的最小间隔 返回 bool 是否满足间距约束 示例 1 nums = [1,0,0,0,1,0,0,1], k = 2 输出: true 示例 2 nums = [1,0,1], k = 2 输出: false C — Concepts（核心思想） 关键观察 只需要记住 上一个 1 的索引 last 当遇到新的 1：若 i - last <= k，说明间隔不足 否则更新 last = i 方法归类 单次线性扫描（One-pass Scan） 事件间距校验（Event Spacing Check） 双指针 / 贪心（Greedy with last pointer） 数学表达 若 i 和 j 是两个 1 的索引（i < j），要求： ...

副标题 / 摘要 一道典型的“乘积 ≥ 阈值”计数题，看起来像是 O(n²) 的双重循环，实际上用「排序 + 二分查找」就能把复杂度压到 O((n+m)log m)。本文从题意抽象、核心公式到多语言实现，带你把这类阈值匹配问题彻底吃透。 预计阅读时长：10~15 分钟 适用场景标签：二分查找、排序计数、阈值匹配 SEO 关键词：spells and potions, successful pairs, 二分查找, lower_bound, 乘积约束 目标读者与背景 目标读者 已熟悉基本二分查找，想提升「在有序数组上做计数」能力的同学 后端 / 算法工程师，经常处理阈值判断与配对统计的问题 准备技术面试，希望积累“排序 + 二分”模板的开发者 为什么这题值得单独写一篇？ 它把一个表面 O(n²) 的「所有配对」问题，转化成了对有序数组的二分计数； 公式非常典型：把 a * b ≥ success 转成 b ≥ ceil(success / a)； 这种思路在推荐系统、风控额度、资源匹配等业务里屡见不鲜。 A — Algorithm（题目与算法） 题目重述 给定两个整数数组 spells 和 potions，以及一个正整数 success。 对于每个咒语 spells[i]，我们定义它与药水 potions[j] 的组合是“成功”的，当且仅当： spells[i] * potions[j] >= success 请返回一个数组 ans，其中 ans[i] 表示第 i 个咒语可以与多少个药水形成成功组合。 ...