链表

副标题 / 摘要 回文链表的核心是“对称比较”，但单链表不能从尾部往前走。最稳的工程化解法是：快慢指针找中点 -> 原地反转后半段 -> 比较 -> 再反转恢复结构，做到 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。 ...

副标题 / 摘要 反转链表是“指针重连”的入门必修课：看似简单，却最容易因为边界、断链、顺序写错而翻车。本文用 ACERS 结构把三指针迭代写法讲透，并给出递归对照与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、链表、指针、迭代 SEO 关键词：Hot100, Reverse Linked List, 反转链表, 三指针, 迭代, 递归, LeetCode 206 元描述：三指针迭代 O(n)/O(1) 反转单链表，附递归对比、工程迁移与多语言实现。 目标读者 正在刷 Hot100 / 准备面试的同学 写链表题经常断链/空指针、希望建立稳定模板的中级开发者 需要在 C/C++/Rust 等语言里熟练处理指针与所有权的工程师 背景 / 动机 在真实工程里，“反转链表”不一定以 LeetCode 的形态出现，但它背后的能力非常通用： 你要在 O(1) 额外空间 下重排节点顺序（例如复用节点对象，避免额外分配） 你要理解 指针重连的顺序：先保留 next，再改 cur.next，否则就会断链 你要能写出 不会特判地狱、对 head = null 也稳的实现 把这题做成模板后，很多链表题（如反转区间、k 组反转、判断回文链表）都会变得顺手很多。 核心概念 单链表：每个节点只有一个 next 指针指向后继 断链风险：一旦把 cur.next 改掉而没保存原来的 next，就丢失后半段 三指针（prev / cur / next）：用 next 暂存后继，再把 cur.next 指向 prev 循环不变量：prev 永远指向“已反转部分”的头；cur 永远指向“未处理部分”的头 A — Algorithm（题目与算法） 题目还原 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 ...

副标题 / 摘要 相交链表的关键不是比较值，而是比较“节点引用/地址”。本文用 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。 ...