LeetCode 链表专题全攻略一个原则、两个考点、三个注意、四个技巧基于 leetcode 题解仓库 linked-list 专题【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 leetcode 题解仓库 thinkings/linked-list.en.md及其中文版 thinkings/linked-list.md为骨架整理而成并辅以仓库内对应题解源码作交叉印证。内容覆盖链表与数组的本质差异、链表增删查基本操作的复杂度、反转与拼接两大考点、环/边界/递归三类高频失误以及虚拟头、快慢指针、穿针引线、先穿再排后判空四个可直接套用的实战技巧。读完本文你既能建立链表题的体系化认知也能从仓库源码层面验证每一个结论。一、引言为什么先啃链表在 LeetCode 上链表标签 下共有54 道题其中 6 道处于锁定状态其余 48 道均已在原仓库作者的专题练习中完成。作者通过集中刷完这 48 道题提炼出一套完整的解题方法即口诀“一个原则两种题型三个注意四个技巧”。在展开口诀之前先建立两个底层认知链表是数据结构的基石队列、栈等线性结构以及树、图等非线性结构底层本质上都是数组和链表这两种存储形态的组合。物理内存由大小相同的内存单元构成数组与链表只是使用物理内存的两种不同方式。链表是一种递归结构每个节点都持有指向下一个节点的指针这决定了链表题可以大量使用递归思维求解。二、链表 vs 数组本质差异与操作复杂度2.1 物理存储差异数组占据连续的内存空间每个单元大小固定因此可以按下标随机访问$O(1)$。链表物理上不连续逻辑顺序通过指针链接实现因此查找只能通过next指针逐个遍历。链表由一系列节点Node构成节点可以在运行时动态生成。单链表每个节点只保存一个后继指针next双向链表还会额外保存前驱指针pre。一个典型的单链表定义如下TypeScript 描述interface ListNodeT { data: T; next: ListNodeT; }其中data是数据域next是指向下一个节点的指针。2.2 操作复杂度对比操作数组链表随机访问$O(1)$$O(N)$需遍历头部插入/删除$O(N)$需移动元素$O(1)$给定前驱指针时尾部插入/删除$O(1)$$O(1)$持有尾指针时给定位置插入/删除$O(N)$$O(1)$一句话概括数组对查询友好、对增删不友好链表则相反适合“数据需要保持一定顺序又需要频繁增删”的场景。2.3 插入操作的伪代码给定插入位置的前驱节点时插入只需三步时间复杂度 $O(1)$temp 待插入位置的前驱节点.next 待插入位置的前驱节点.next 待插入指针 待插入指针.next temp提示 1务必考虑头节点与尾节点两种边界情况。 提示 2新手推荐先画图、再写代码熟练之后自然可以脱离画图。2.4 删除操作的伪代码删除只需把前驱节点的next修正为其下下个节点时间复杂度同样 $O(1)$待删除位置的前驱节点.next 待删除位置的前驱节点.next.next同样要注意边界条件头尾指针情况。2.5 遍历的伪代码迭代版本当前指针 头指针 while 当前节点不为空 { print(当前节点) 当前指针 当前指针.next }前序遍历的递归版本dfs(cur) { if (当前节点为空) return print(cur.val) return dfs(cur.next) }三、链表和数组到底有多大差异原文档给出的核心观点是数组和链表同为线性结构逻辑上高度相似差异只在细微的操作细节与使用场景而使用场景在题目中难以直接考察做题时真正要关注的是操作细节。3.1 遍历逻辑相同细节不同数组遍历for(int i 0; i arr.size(); i) { print(arr[i]); }链表遍历for (ListNode cur head; cur ! null; cur cur.next) { print(cur.val); }差异仅在于数组是“索引 ”链表是cur cur.next。3.2 逆序遍历链表需要记录前驱数组可以轻松逆序for(int i arr.size() - 1; i -1; i--) { print(arr[i]); }链表逆序通常依赖双向链表的pre指针for (ListNode cur tail; cur ! null; cur cur.pre) { print(cur.val); }但 LeetCode 的双向链表题目极少大多数场景下无法直接拿到前驱节点这就是为什么链表的遍历/反转代码里总要自己维护一个前驱指针pre的根本原因。3.3 尾部追加链表的“push”数组push一个元素arr.push(1);链表在多数语言中没有内置类型力扣通常用如下类模拟public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }自己实现“push”只需两行假设tail是链表尾节点tail.next new ListNode(lucifer); tail tail.next;执行后tail仍然指向尾节点。这个技巧在“复制一个新链表”类题目中非常实用先开辟新链表头再不断拼接复制的节点。数组push的底层实现逻辑也类似arr.length 1; arr[arr.length - 1] lucifer;不建议的做法把链表先转成数组再做题。这等于否认链表的价值会丢失对链表操作细节的训练。四、链表题难度几何原文档的结论是链表题整体不难。以 LeetCode 为例链表标签下的困难题只有 2 道第 23 题合并 K 个升序链表基本不涉及复杂链表操作本质是归并排序思想 “合并两个有序链表”后者本身就是简单题。会数组归并排序和合并两个有序链表即可拿下。第 25 题K 个一组翻转链表读完本专题内容即可掌握其题解见 problems/25.reverse-nodes-in-k-groups.md。虽然难度不高但初学者常见的痛点集中在“指针绕来绕去就绕晕了”“老是死循环”。为此原文档给出了整套口诀一个原则两种题型三个注意四个技巧。五、一个原则画图画图是贯穿链表题目的准则尤其对新手降低认知负担链表题指针关系复杂内存容量短期记忆有限。把脑子里的结构画到纸上相当于把“寄存器”里放不下的数据放到“内存”让思维聚焦在真正关键的指针关系上。不追求美观画得难看没关系能看清节点之间的关系即可随手勾画就够。画图不仅仅是防 bug 的手段也是分析一切链表题包括反转、拼接、环检测的第一性方法。六、两个考点把 48 道链表题刷完后可以发现链表的考点非常单一除设计类题目外只有两点——指针的修改与链表的拼接。6.1 考点一指针的修改以反转链表为代表数组支持随机访问反转只需头尾交换function reverseArray(arr) { let left 0; let right arr.length - 1; while (left right) { const temp arr[left]; arr[left] arr[right]; arr[right--] temp; } return arr; }链表反转则不同其核心就是修改指针。原文档给出了一个“反转任意一段链表”的通用模板签名如下reverse(self, head: ListNode, tail: ListNode)其中head是需要反转的头节点tail是需要反转的尾节点。若head、tail分别是整条链表的头和尾则反转整个链表否则反转局部链表。推理过程务必画图验证由于链表是递归结构只需反转相邻两个节点其余节点以同样方式处理。两个节点的反转就是一次指针修改cur.next pre。但这一步有两个副作用“分道扬镳”修改前必须记录后继否则后续节点丢失next cur.next; cur.next pre; cur next;“成环”从前往后遍历时前面的链表已经被反转因此前序遍历场景下环不会真正产生画图时需按正确顺序理解节点指向。第一版实现注意tail本身未被反转# 翻转一个子链表并返回新的头与尾 def reverse(self, head: ListNode, tail: ListNode): cur head pre None while cur ! tail: # 留下联系方式 next cur.next # 修改指针 cur.next pre # 继续往下走 pre cur cur next # 返回反转后的新头尾节点 return tail, head修正版把tail之后的一个节点terminal作为终止条件传入即可让tail也参与反转class Solution: # 翻转一个子链表并且返回新的头与尾 def reverse(self, head: ListNode, tail: ListNode, terminal: ListNode): cur head pre None while cur ! terminal: # 留下联系方式 next cur.next # 修改指针 cur.next pre # 继续往下走 pre cur cur next # 返回反转后的新头尾节点 return tail, head仓库源码印证完整反转整条链表的迭代实现见 problems/206.reverse-linked-list.md其 Python 版本使用多变量同时赋值本质与上面模板完全一致class Solution: def reverseList(self, head: ListNode) - ListNode: if not head: return None prev None cur head while cur: cur.next, prev, cur prev, cur, cur.next return prev该题解同时给出了递归版本与复杂度分析迭代 $O(N)$ 时间、$O(1)$ 空间递归 $O(N)$ 时间、$O(N)$ 空间并明确指出“递归会导致栈使用线性增长长链表下有爆栈风险”可作为理解“前后序”章节的补充素材。6.2 考点二链表的拼接链表题为什么总在“穿来穿去”拼接因为链表的存在价值就是不要求物理内存连续性、对插入删除友好拼接正是这一设计初衷的直接体现。典型应用包括反转链表 II局部反转后与前后段拼接合并有序链表第 25 题 K 个一组翻转链表、第 61 题旋转链表、第 92 题反转链表 II 等。只要掌握了第二节的基本操作再注意环与边界问题拼接类题目不难应对完整的拼接套路在“穿针引线”技巧中展开。七、三个注意原文档指出链表 90% 的常见错误集中在三种情况出现了环造成死循环分不清边界导致边界条件出错搞不懂递归怎么做。7.1 环环的考点分两类题目本身有环判断是否有环、找环的入口用快慢指针算法解决见“快慢指针”技巧仓库题解 problems/142.Linked-List-Cycle-II.md 提供了完整的快慢指针推导。题目没环但操作指针时整出环这是本文讨论的重点。避免操作成环最有效的措施就是画图——两个或几个节点互相引用构成环图上一眼就能看出。实操技巧是先画图然后把每个指针操作都反映到图中。由于链表是递归结构很多问题天生具有递归性如反转链表画图时只需画出其中一个子结构即可不必把整条链画完具体见 7.3 前后序。7.2 边界边界错误多源于没有考虑头尾节点等特殊情况。原文档给出了两个关键技巧头节点可能被移除时使用虚拟节点让头节点变成中间节点无需为其做特殊判断详见“虚拟头”技巧。题目要求返回的不是原头节点而是尾节点或中间节点注意指针变化必要时借助虚拟头在“恰当的时候断开链接”。7.3 前后序递归思维链表结构天生递归用递归思维解题事半功倍。前中后序的本质指当前节点相对子节点的处理顺序。先处理当前节点再处理子节点是前序先处理左子再处理当前节点最后处理右子是中序最后处理当前节点是后序。实际代码中往往同时存在“进入前后”与“退出之后”的逻辑原文档的建议是只关注主逻辑的位置——主逻辑在前就是前序遍历在后就是后序遍历。绝大多数链表题是单链表单链表只有一个后继指针因此只有前序和后序没有中序遍历。以反转链表为例前序写法主逻辑“改指针”在递归进入子节点之前def dfs(head, pre): if not head: return pre next head.next # 主逻辑改变指针在前面 head.next pre dfs(next, head) dfs(head, None)后序写法主逻辑在递归返回过程中执行def dfs(head): if not head or not head.next: return head res dfs(head.next) # 主逻辑改变指针在递归返回的过程执行 head.next.next head head.next None return res为什么两种写法边界、入参、代码都不同原文档给出了一句非常精炼的判断标准如果是前序遍历你可以想象前面的链表都处理好了怎么处理的不用管如果是后序遍历你可以想象后面的链表都处理好了怎么处理的不用管。前序画图要点只聚焦中间的框子结构同时记住两点——前面的已处理好、后面的还没处理。据此写代码后面的没处理所以要用head.next定位下一个节点“留下联系方式”前面的已处理完所以head.next pre不会成环。后序画图要点通过head.next拿到下一个元素再让下一个元素的next指向自身head.next.next head即可完成反转。但画图后会发现这里明显存在一个环——这正是画图的价值所在直观暴露问题。解决办法是把head.next置空def dfs(head): if not head or not head.next: return head res dfs(head.next) head.next.next head # 置空防止环的产生 head.next None return res推荐前序前序遍历很容易改造成“不需要栈”的迭代而后序遍历主逻辑位于函数调用栈的弹出阶段必须借助栈。这也是为什么原文档建议“递归和迭代都要写时选前序”。写递归的技巧插播想象已经处理好的部分数据并“用手挡起来”只思考“如何根据已处理数据与当前数据推导还未处理的数据”。仓库中 problems/206.reverse-linked-list.md 的后序递归实现Python正好印证了上述后序模板class Solution: def reverseList(self, head: ListNode) - ListNode: if not head or not head.next: return head ans self.reverseList(head.next) head.next.next head head.next None return ans八、四个技巧8.1 虚拟头先用三个小测验建立“指针指向”的直觉答案附后建议先自己推理Q1ans.next最终指向什么ans ListNode(1) ans.next head head head.next head head.nextA1最开始的head。Q2ans.next最终指向什么ans ListNode(1) head ans head.next ListNode(3) head.next ListNode(4)A2ListNode(4)。Q3ans.next最终指向什么ans ListNode(1) head ans head.next ListNode(3) head ListNode(2) head.next ListNode(4)A3ListNode(3)。解读ans.next指向什么取决于“最后切断ans.next指向的位置在哪里”。Q1 中head head.next只是移动了head这个引用ans与head的联系被切断ans本身未变。Q2 中head与ans始终指向同一节点head.next被连续赋值最终ans.next是ListNode(4)。Q3 中执行head ListNode(2)后head与ans的关系被彻底切断此后所有head操作都不会影响ans因此ans.next仍是被切断前指向的ListNode(3)。理解这个“切断关系”的机制是掌握虚拟头的前提——指针操作是链表的核心基础不牢则后续寸步难行。虚拟头的两大作用把头节点变成中间节点简化判断头节点是最常见的边界。用一个虚拟头指向原头节点后虚拟头成为“新的头节点”它不参与运算、无需特殊判断。例如删除头节点时不再需要单独的分支处理。在合适的时候断开链接返回中间节点新建虚拟头并让其在“刚好指向需要返回的节点”时断开连接最后返回虚拟头.next。第 25 题 K 个一组翻转链表 就用到了这个技巧。该技巧同样适用于二叉树等问题例如“返回二叉树最左下节点”。8.2 快慢指针适用场景一环检测与环入口。判断链表是否有环、找环入口直接使用快慢指针即可解决——这类题属于“不知道就不会、知道了就不容易忘”的类型学一次写一道题即可掌握。仓库题解 problems/142.Linked-List-Cycle-II.md 中完整给出了快慢指针的推导慢指针每次走一步、快指针每次走两步两者相遇即存在环再结合数学推导可定位环入口。适用场景二链表不支持随机访问取特定位置元素需要特殊手段找中间项两个指针快指针一次走两步、慢指针一次走一步。快指针走到头时慢指针刚好在中间。找倒数第 K 项让快指针先走 K 步再快慢指针同步走。快指针到头时慢指针刚好在倒数第 K 项。这类技巧属于“会了就容易、且不容易忘不会就很难想出”的类型建议学完用几道题巩固。8.3 穿针引线拼接链表这是针对“考点二拼接链表”的具体套路名称是原文档作者自创的起名字是为了方便记忆。该方法通常不是最优解但好理解、方便书写、不易出错推荐新手使用。以“反转链表的中间一部分”为例假设中间部分已经反转好剩下的是如何把它拼回去。从左到右给断点编号。两个断点共涉及四个节点依次记为a、b、c、da、d分别是要反转部分的前驱与后继不参与反转b、c是要反转部分的头与尾参与反转。除了cur多用两个指针pre和next即可定位a、b、c、d。找到后直接“穿针引线”a.next c b.next d一次拼接即完成清晰且不混乱。第 25 题、第 61 题旋转链表、第 92 题反转链表 II都适合用此套路。8.4 先穿再排后判空这是四个技巧中的最后一个实操价值很大。以反转链表循环体为例cur head pre None while cur ! tail: # 留下联系方式 next cur.next # 修改指针 cur.next pre # 继续往下走 pre cur cur next # 反转后的新的头尾节点返回出去问题next cur.next与cur.next pre谁先谁后什么时候要判空口诀拆解先穿穿 修改指针含反转的指针修改与穿针引线的指针修改。先不要管顺序先把“穿”的代码全部写上。再排穿完以后代码总量已定接下来只做排列组合消除 bug。两行代码应先next cur.next再cur.next pre——因为cur.next pre执行后cur.next就被改了链表在此处断开后面的节点全部访问不到。更一般地只需考虑“被改变 next 指针”的那部分代码的顺序其他代码不需要逐一推敲。后判空同理穿完以后只需检查哪行代码会空指针异常且只需要检查“被改变 next 指针”相关的位置。例如while cur: cur cur.nextwhile条件已保证cur非空无需判空。而while cur: next cur.next n_next next.next第二个next是可能为空的当next是链尾节点时必须判空while cur: next cur.next if not next: break n_next next.next九、总结与题目推荐核心结论回顾画图是唯一入门捷径能画出图、并能根据图完成指针操作即算入门——甭管代码有没有 bug。考点只有两个指针操作典型是反转与链表拼接。二者既是链表精髓也是主要考点。易错点有三处环多为指针操作残留需画图聚焦子结构、边界头节点判断是大头善用虚拟节点、前后序递归时先明确自己写的是前序还是后序前序只思考“前面的已处理好”后序只思考“后面的已处理好”。数组与链表逻辑神似单链表无法 $O(1)$ 拿到前驱节点是因为链表的增删操作天然依赖前驱节点——这是链表特性决定的也是遍历时总要维护pre的原因。递归与迭代都写时推荐前序遍历前序容易改造成不需要栈的迭代。一点澄清本文讨论的“链表题”指的是“入参是链表、且需要对链表本身进行操作”的题目。若某题需要归并排序、前缀和等其他算法如第 23 题合并 K 个链表那些算法本身不在本专题范围内。推荐练习清单用今天学到的知识逐一解决21. 合并两个有序链表82. 删除排序链表中的重复元素 II83. 删除排序链表中的重复元素86. 分隔链表92. 反转链表 II138. 复制带随机指针的链表141. 环形链表142. 环形链表 II143. 重排链表148. 排序链表206. 反转链表234. 回文链表仓库内可进一步研读的题解反转链表迭代/递归双版本见 problems/206.reverse-linked-list.mdK 个一组翻转的分组反转拼接全流程见 problems/25.reverse-nodes-in-k-groups.md环检测与环入口的快慢指针推导见 problems/142.Linked-List-Cycle-II.md。链表数据结构基础可参考 thinkings/basic-data-structure.md二叉树遍历前中后序概念的源头可参考 thinkings/binary-tree-traversal.md。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考