链表

副标题 / 摘要 这题不是“背答案题”，而是缓存系统的基本功：如何在常数时间内同时满足“快速访问”和“按最近最少使用淘汰”。本文从朴素方案推到最优结构，并给出可运行的多语言实现。 预计阅读时长：14~18 分钟 标签：LRU、哈希表、双向链表、系统设计 SEO 关键词：LRU Cache, LeetCode 146, 哈希表, 双向链表, O(1) 元描述：通过哈希表 + 双向链表实现 LRU 缓存，get/put 平均 O(1)，附工程场景、常见坑与六语言实现。 目标读者 正在刷 LeetCode 中等题、想吃透“数据结构组合技”的同学 做后端/中间件，需要实现或优化本地缓存的工程师 面试中经常被问到 LRU，但只记住结论、没掌握细节的人 背景 / 动机 缓存是“空间换时间”，但空间是有限的。 当缓存满了，必须淘汰一些键。LRU（Least Recently Used，最近最少使用）假设： 最近被访问的数据，将来更可能再次访问 很久没访问的数据，优先淘汰更合理 工程里常见于： 接口响应缓存 数据库热点记录缓存 页面/会话本地状态缓存 核心概念 LRU 策略：淘汰“最久未使用”的键 访问即更新新鲜度：get 成功后要把该 key 标为“最近使用” 容量约束：put 新 key 造成超容时，需要立即驱逐一个最旧键 O(1) 平均复杂度：get 和 put 都不能线性扫描 A — Algorithm（题目与算法） 题目重述 设计并实现一个满足 LRU 约束的数据结构 LRUCache： LRUCache(int capacity)：用正整数容量初始化 int get(int key)：若 key 存在返回 value，否则返回 -1 void put(int key, int value)： key 已存在：更新 value，并视作最近使用 key 不存在：插入新键值对 若超出容量：淘汰最久未使用的 key 并要求 get 和 put 平均时间复杂度为 O(1)。 ...

副标题 / 摘要 这道题的难点不是遍历链表，而是正确复制 random 指针所形成的“跨节点引用关系”。本文从朴素思路推导到哈希映射法，讲清为什么它稳定、可维护、易工程落地。 预计阅读时长：12~16 分钟 标签：链表、深拷贝、哈希表、随机指针 SEO 关键词：LeetCode 138, Copy List with Random Pointer, 随机链表复制, 深拷贝, 哈希映射 元描述：用两趟遍历 + 映射表完成随机链表深拷贝，系统讲解正确性、复杂度、工程实践与六语言实现。 目标读者 刷 LeetCode 时对 random 指针题目不够稳的开发者 想厘清“浅拷贝 vs 深拷贝”差异的同学 希望把算法思路迁移到工程对象复制场景的工程师 背景 / 动机 普通链表只要复制 val 和 next，逻辑很直观； 但随机链表多了一个 random 指针，它可能： 指向任意节点（前面、后面、自己） 也可能是 null 这使问题从“线性复制”变成“带额外引用关系的结构复制”。 工程里常见等价问题： 复制工作流节点对象，同时保留跨步骤跳转关系 复制缓存对象图，保持对象间引用一致 复制会话链，保持回溯/快捷索引引用 核心概念 浅拷贝（Shallow Copy）：只复制节点壳，内部引用仍指向旧对象 深拷贝（Deep Copy）：新建完整对象图，所有引用都指向新对象 节点身份映射：old_node -> new_node，是重建 random 的关键 结构等价：新链表应与旧链表在值与指针关系上同构，但完全不共享节点 A — Algorithm（题目与算法） 题目重述 给定一个长度为 n 的链表，每个节点有： val next random（可指向任意节点或 null） 要求构造该链表的深拷贝并返回新头节点。 新链表中的任何指针都不能指向原链表节点。 ...

副标题 / 摘要 这题的核心不是“删除节点”，而是“如何在单链表里定位倒数第 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 个结点，并返回链表的头结点。 ...

副标题 / 摘要 这题本质是把「小学竖式加法」搬到链表：同位相加、处理进位、走到末尾后可能还要补一个新节点。文章将从朴素思路推到最优单遍解法，并给出工程场景与多语言实现。 预计阅读时长：12~15 分钟 标签：链表、进位、模拟、LeetCode 2 SEO 关键词：Add Two Numbers, 两数相加, 逆序链表, 进位, LeetCode 2 元描述：用哨兵节点 + 单遍遍历在 O(max(m,n)) 时间完成两条逆序数字链表求和，附常见坑、工程应用和六语言代码。 目标读者 刚开始刷链表题，想建立稳定解题模板的同学 对「进位」和「边界处理」容易写错的中级开发者 希望把算法思维迁移到工程数据流处理的工程师 背景 / 动机 看似只是 LeetCode 入门题，但它练的能力非常实用： 多输入流同步推进（l1、l2 两个指针） 状态跨轮传播（carry 进位） 边界完整性（长度不同、最后一位进位） 这三点在工程里非常常见，例如金额分片累加、多源日志计数合并、流式统计补位等。 核心概念 逆序存储：个位在链表头部，十位在下一节点，以此类推 逐位相加：每轮只处理一个位，值来自 x + y + carry 进位传播：carry = sum // 10，当前位 digit = sum % 10 哨兵节点（dummy）：避免首次插入时区分“头节点是否为空” A — Algorithm（题目与算法） 题目重述 给你两个非空链表，表示两个非负整数。 数字按逆序存储，且每个节点存储一位数字。 请将两个数相加，并返回同样逆序存储的结果链表。 题目保证除数字 0 外，这两个数都不会以 0 开头。 输入输出描述 项目 含义 输入 两个链表 l1、l2，每个节点值在 0~9 输出 一个新链表，表示 l1 + l2 的结果（逆序） 示例 1 输入: l1 = [2,4,3], l2 = [5,6,4] 解释: 342 + 465 = 807 输出: [7,0,8] 示例 2 输入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 解释: 9999999 + 9999 = 10009998 输出: [8,9,9,9,0,0,0,1] 思路推导：从朴素到最优 朴素思路 1：先转整数再相加 把链表转成整数 n1、n2 做 n1 + n2 再把结果拆位转回链表 问题： ...

副标题 / 摘要 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 思路推导（从朴素到最优） 朴素做法：转数组再排序 遍历链表把值放到数组 调库排序后重建链表 问题： ...

副标题 / 摘要 这题本质是“k 路归并”。如果直接一条条串行并入，性能会退化；用分治按二叉树方式两两合并，能把复杂度优化到 O(N log k)。本文按 ACERS 模板把思路推导、工程映射和多语言实现一次讲透。 预计阅读时长：12~16 分钟 标签：Hot100、链表、分治、归并 SEO 关键词：Merge k Sorted Lists, 合并K个升序链表, 分治归并, LeetCode 23, O(N log k) 元描述：从串行归并到分治归并，系统讲解 LeetCode 23 的最优复杂度解法与工程实践。 目标读者 正在刷 Hot100，已经掌握 LeetCode 21 的同学 想把“双链表归并”升级为“k 路归并模板”的开发者 在服务端做多路有序流合并（日志、时间线、分片结果）的工程师 背景 / 动机 LeetCode 23 是 LeetCode 21 的自然升级版： 21：2 路归并 23：k 路归并 核心挑战不在“能不能合并”，而在“如何把复杂度控制在可接受范围”。 如果每次把结果链表继续和下一条链表做串行归并，早期节点会被反复遍历，实际性能很容易退化。 核心概念 N：所有链表节点总数 k：链表条数 串行归并：从左到右不断把当前结果和下一条链表合并 分治归并：像归并排序一样，两两合并，按层收敛 最小堆方案：维护 k 个当前头节点，每次弹出最小值并推进其所在链表 A — Algorithm（题目与算法） 题目还原 给你一个链表数组 lists，每个链表都按升序排列。 请将所有链表合并到一个升序链表中，并返回合并后的头节点。 输入输出 名称 类型 描述 lists ListNode[] k 条升序链表，元素可为空 返回 ListNode 合并后的升序链表头节点 示例 1 输入: lists = [[1,4,5],[1,3,4],[2,6]] 输出: [1,1,2,3,4,4,5,6] 示例 2 输入: lists = [] 输出: [] C — Concepts（核心思想） 思路推导：从朴素到最优 朴素法 A：拉平到数组后排序 ...

副标题 / 摘要 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 指针再次到达，则链表中存在环。 ...