快慢指针

副标题 / 摘要 这题的核心不是“删除节点”，而是“如何在单链表里定位倒数第 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 148 的核心不是“会排序”，而是“在链表结构里选对排序算法”。数组可随机访问适合快排/堆排，而单链表最匹配的是归并排序：找中点、递归分治、线性归并。 预计阅读时长：12~16 分钟 标签：Hot100、链表、归并排序、分治 SEO 关键词：Sort List, 排序链表, 链表归并排序, LeetCode 148, Hot100 元描述：用链表归并排序在 O(n log n) 内完成排序，覆盖思路推导、工程迁移、复杂度分析和多语言可运行实现。 目标读者 正在刷 Hot100，想把链表题模板系统化的同学 做链表题经常在“切分和拼接”环节出错的开发者 想搞清楚“为什么链表排序优先用归并”而不是快排的人 背景 / 动机 链表排序在工程里并不罕见： 合并来自多个来源的链式任务队列 对按时间追加的链式日志做离线整理 对内存敏感结构进行“尽量少拷贝”的重排 如果把数组排序思维直接搬过来，往往会遇到： 链表不支持 O(1) 随机访问，分区/堆操作代价高 频繁节点移动容易写出复杂且脆弱的代码 所以这题本质是：为链表选择正确的数据结构友好算法。 核心概念 分治（Divide & Conquer）：把链表二分到最小子问题，再向上合并 快慢指针找中点：slow 每次 1 步，fast 每次 2 步 链表归并：两个有序链表线性拼接成一个有序链表 稳定排序：相等元素相对次序可保持 A — Algorithm（题目与算法） 题目还原 给你链表头节点 head，请将其按升序排序并返回排序后的链表。 要求时间复杂度为 O(n log n)。 输入输出 名称 类型 描述 head ListNode 单链表头节点（可能为空） 返回 ListNode 升序排序后的头节点 示例 1 输入: 4 -> 2 -> 1 -> 3 输出: 1 -> 2 -> 3 -> 4 示例 2 输入: -1 -> 5 -> 3 -> 4 -> 0 输出: -1 -> 0 -> 3 -> 4 -> 5 思路推导（从朴素到最优） 朴素做法：转数组再排序 遍历链表把值放到数组 调库排序后重建链表 问题： ...

副标题 / 摘要 这题的价值在于把“判环”升级为“定位入环点”。最稳的工程化模板是 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 结构讲透 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 指针再次到达，则链表中存在环。 ...

副标题 / 摘要 回文链表的核心是“对称比较”，但单链表不能从尾部往前走。最稳的工程化解法是：快慢指针找中点 -> 原地反转后半段 -> 比较 -> 再反转恢复结构，做到 O(n) 时间、O(1) 额外空间且不破坏链表。 预计阅读时长：10~14 分钟 标签：Hot100、链表、快慢指针、原地反转 SEO 关键词：回文链表, Palindrome Linked List, O(1) 空间, 快慢指针, 反转后半段, LeetCode 234 元描述：快慢指针定位中点，反转后半段与前半段逐一比较，最后恢复链表结构；O(n)/O(1) 判断单链表是否回文。 目标读者 刷 Hot100，想掌握“链表中点 + 原地反转”组合拳的学习者 面试中经常遇到“回文/对称/镜像”类题的开发者 关注空间效率、且需要保证数据结构不被破坏的工程实践者 背景 / 动机 在数组里判断回文很简单：左右指针向中间收缩即可。 但在单链表里，你只能顺着 next 单向走，无法从尾部回看，这就让“对称比较”变得不那么直接。 工程上常见的约束也与题目一致： 结构不能改（不能改值、不能打标记、不能改 next 永久化） 额外内存有限（不想把所有节点拷贝到数组里） 因此我们需要一个 线性时间、常数空间、且能恢复结构 的模板解法。 核心概念 概念 含义 作用 回文 从左到右与从右到左相同 需要做“对称比较” 快慢指针 fast 每次两步、slow 每次一步 O(n) 找到链表中点 原地反转 改指针方向把链表片段反转 把“后半段”变成可从前往后比较 结构恢复 比较完成后再反转回去并接回 满足“链表保持原结构”要求 A — Algorithm（题目与算法） 题目还原 给你一个单链表的头节点 head，请你判断该链表是否为回文链表： 如果是回文，返回 true；否则返回 false。 ...