链表题解方法论leetcode 仓库链表专题「一个原则、两个考点、三个注意、四个技巧」实战指南【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读链表是各类数据结构队列、栈、树、图在物理存储层最常见的底层形态之一也是 LeetCode 面试题中出现频率最高的专题之一。本文基于 leetcode 仓库 thinkings/linked-list.md 专题文档系统梳理链表的物理本质、基本操作与复杂度、数组对比以及作者提炼的解题口诀「一个原则、两个考点、三个注意、四个技巧」并结合仓库中 92. 反转链表 II、25. K 个一组翻转链表、142. 环形链表 II、61. 旋转链表 等题解源码帮助读者建立从原理到实战的完整链表解题框架。引言链表专题的整体图景链表在 LeetCode 的 linked list 标签下共有54 道题。作者在准备该专题时花数天时间将几乎全部链表题目刷完除六道加锁题目外并由此归纳出一个结论链表题的考点非常单一除设计类题目外本质上只考察两件事——指针的修改与链表的拼接。正因如此只要掌握了正确的方法论链表题并不难LeetCode 平台中链表标签下处于困难Hard难度的题目只有两道23. 合并 K 个升序链表基本没有复杂的链表操作用常规的归并排序即可解决核心前置是「合并两个有序链表」这一简单题25. K 个一组翻转链表即仓库中的 25.reverse-nodes-in-k-groups.md在掌握下文的反转子链表模板后可以轻松拿下。合并两个有序数组同样是简单题其难度与合并两个有序链表几乎一致。相关解法可参考 21.merge-two-sorted-lists.en.md。针对「指针绕来绕去就绕晕」「老是死循环」等常见痛点作者总结了六字口诀一个原则两个考点三个注意四个技巧。下文将逐项展开。链表基础从物理内存到逻辑结构数组与链表物理内存的两种使用方式各种数据结构——无论是队列、栈等线性结构还是树、图等非线性结构——从根本上讲底层都是数组和链表。物理内存由一个个大小相同的内存单元构成而数组和链表正是使用这些物理内存的两种不同方式数组占用连续的内存空间每个单元大小固定因此可以按下标随机访问但也因为空间紧密相连头部的插入和删除复杂度为 O(N)平均复杂度也是 O(N)只有尾部插入/删除为 O(1)。链表物理存储单元上非连续、非顺序数据元素的逻辑顺序通过节点中的指针链接次序实现链表的查找依赖 next 指针遍历因此不支持随机访问。一句话概括数组对查询友好、对增删不友好链表则相反。链表适合数据需要保持一定顺序、但又要频繁增删的场景。图 1 至图 3物理内存图、数组与链表物理存储对比图、链表逻辑表示图为作者绘制于专题文档中因仓库内无对应静态资源文件此处以文字描述代替图示读者可结合自绘示意图理解。单链表的定义与结构链表由一系列节点结点组成节点可在运行时动态生成。一个典型的单链表节点定义如下TypeScriptinterface ListNodeT { data: T; next: ListNodeT; }其中data是数据域存放数据next是指向下一个节点的指针后驱节点。若是双向链表还会有一个前驱节点pre。力扣平台通常使用如下 Java 类模拟链表节点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; } }一个有趣的视角链表其实就是特殊的树即「一叉树」。这也是链表天然具有递归性的原因后文的「前后序」部分会利用这一点。链表的基本操作与复杂度插入插入只需要考虑插入位置的前驱节点和后继节点双向链表还需要更新后继节点其他节点不受影响。因此在给定前驱节点指针的情况下插入的时间复杂度为 O(1)若未给定指针需先遍历查找节点最坏情况下为 O(N)。伪代码temp 待插入位置的前驱节点.next 待插入位置的前驱节点.next 待插入指针 待插入指针.next temp提示 1考虑头尾指针的情况提示 2新手推荐先画图再写代码熟练后可省略画图。删除删除只需将待删除节点的前驱节点的 next 指针修正为其下下个节点注意考虑边界条件。伪代码待删除位置的前驱节点.next 待删除位置的前驱节点.next.next遍历迭代伪代码当前指针 头指针 while 当前节点不为空 { print(当前节点) 当前指针 当前指针.next }前序遍历风格的递归伪代码dfs(cur) { if 当前节点为空 return print(cur.val) return dfs(cur.next) }数组与链表操作细节的「神相似」作者强调数组和链表同为线性结构二者在逻辑上有很多相似之处只是在细微操作和使用场景上有差异而使用场景在题目中很难直接考察。对比以下两段遍历代码// 数组遍历 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」。再看逆序遍历// 数组逆序遍历 for(int i arr.size() - 1; i -1; i--) { print(arr[i]) } // 链表逆序遍历需双向链表 for (ListNode cur tail; cur ! null; cur cur.pre) { print(cur.val) }单链表无法在 O(1) 时间内拿到前驱节点这也是为什么很多题解中需要自行维护一个前驱节点pre。向尾部追加元素push数组可以直接arr.push(1)底层近似为「扩容 尾部赋值」而链表没有内置的 push 方法需要自行实现// 假设 tail 是链表的尾部节点 tail.next new ListNode(lucifer) tail tail.next这两行代码执行后tail 依然指向尾部节点。这个技巧在复制链表、逐个拼接新节点时非常实用。作者特别提醒不建议把链表先转成数组再做这种做法等于否定了链表存在的价值。一个原则画图画图是贯穿所有链表题目的准则尤其对于新手无论简单题还是难题都要画图。画图的作用与打草稿、写备忘录同理把存在脑子里的东西放到纸上减少认知负担——可以把大脑比作 CPU、脑内记忆比作寄存器寄存器容量有限需要把不常用的信息放到「内存」纸、平板等一切可画图介质里。画得好不好看不重要能看清关系即可。两个考点考点一指针的修改指针修改最典型的代表就是链表反转。对数组这种支持随机访问的结构反转很容易头尾不断交换即可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; }而链表反转则麻烦得多力扣中反转类题目非常多。作者给出了一个可复用的任意一段链表反转模板# 翻转一个子链表并返回新的头与尾 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其中head是需要反转的头节点tail是需要反转的尾节点。若 head 是整个链表的头、tail 是整个链表的尾即反转整个链表否则就是反转局部链表。实现要点这也是画图价值的直接体现仅用cur.next pre一步修改指针会同时造成两个问题一是可能产生环导致死循环二是让链表「分道扬镳」。因此反转前必须先记录下一个节点next cur.next cur.next pre cur next关于环因为从前往后遍历时前面的链表已经被反转实际并不会成环图需要按正确的遍历顺序绘制。tail 本身没有被反转从上面的循环条件cur ! tail可见tail 并未参与反转。解决办法是把 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这个带terminal的版本正是 25. K 个一组翻转链表 Python 解法中reverse函数的原始模板——仓库题解中reverseKGroup每 k 个一组调用self.reverse(head, tail, tail.next)随后用pre.next head、tail.next next把子链表重新接回原链表见 25.reverse-nodes-in-k-groups.md。考点二链表的拼接链表题总喜欢「穿来穿去」拼接比如反转链表 II、合并有序链表等。这并非偶然而是链表的本质价值所在链表不必要求物理内存连续对插入和删除友好因此拼接类操作天然高频出现。掌握了上文的基本操作配合下文「穿针引线」技巧拼接类题目即可迎刃而解。三个注意链表题最容易出错的 90% 集中在以下三种情况环死循环、边界条件、递归前后序。注意一环环的考点有两类题目本身就有环让你判断是否有环以及环的位置——这类问题用「快慢指针」解决下文展开题目链表本来无环但操作指针时被「整出环」了——这是本文重点讨论的场景。避免出现环最有效的措施就是画图如果两个或几个节点构成了环通过图很容易看出来。实操技巧是先画图然后把对指针的每一次操作都反映到图中。由于链表是递归的数据结构很多链表问题如反转天生具有递归性只需画出其中一个子结构即可不需要画出整个链表。注意二边界很多人出错是没有考虑边界。考虑边界的一个技巧是仔细看题目信息如果题目的头节点可能被移除考虑使用虚拟节点这样头节点就变成了中间节点无需为头节点做特殊判断如果题目要求返回的不是原本的头节点而是尾部节点或其他中间节点要注意指针的变化。具体内容在「四个技巧」的虚拟头部分展开。注意三前后序链表结构天生具有递归性使用递归思维解题往往事半功倍。仓库的 thinkings/binary-tree-traversal.md 详细讲解了二叉树的前序、中序、后序三种遍历前中后序指的是当前节点相对子节点的处理顺序。而绝大多数链表题都是单链表只有一个后继指针因此只有前序和后序没有中序遍历。判断前序还是后序关键是看主逻辑改变指针的代码的位置主逻辑在进入子节点之前执行是前序在递归返回过程中执行是后序。以一个同时包含 pre/post 逻辑的代码为例def traverse(root): print(pre) traverse(root.left) traverse(root.righ) print(post)以反转链表为例前序遍历写法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两种写法的边界、入参、代码均不同。记忆口诀很简单前序遍历想象前面的链表都已经处理好了怎么处理的不必管只聚焦子结构此时前面的链表不会成环后面的链表还没处理因此需要通过next head.next留下联系方式后序遍历想象后面的链表都已经处理好了只聚焦子结构此时可以通过head.next.next head完成反转但会临时产生环因此需要将head.next置空如head.next None来防止环。后序遍历之所以要置空从图中可以非常直观地看出head.next.next head之后两个节点互相引用形成环置空head.next即可打破。推荐使用前序遍历前序遍历容易改造成不需要栈的迭代写法而后序遍历的主逻辑在函数调用栈的弹出过程必须借助栈完成。这一点可以从上文「迭代版反转」与「前序递归版反转」的对比中看出——两者的指针操作顺序完全一致。写递归的一个技巧想象自己已经处理好了部分数据并「用手挡起来」剩下的部分还没处理接下来思考「如何根据已处理的数据和当前数据推导出还未处理的数据」。四个技巧技巧一虚拟头dummy head先做三个小测验考察对指针引用关系的理解Q1如下代码ans.next指向什么ans ListNode(1) ans.next head head head.next head head.nextA1最开始的 headans.next指向的是被head head.next切断前的原 head 节点head的重新赋值不影响ans。Q2如下代码ans.next指向什么ans ListNode(1) head ans head.next ListNode(3) head.next ListNode(4)A2ListNode(4)head与ans仍指向同一对象head.next被连续修改为 ListNode(3)、ListNode(4)ans.next同步变化。Q3如下代码ans.next指向什么ans ListNode(1) head ans head.next ListNode(3) head ListNode(2) head.next ListNode(4)A3ListNode(3)关键在head ListNode(2)这一行它切断了head与ans的引用关系此后对head的一切操作都不再影响ans。核心规律ans.next指向什么取决于最后一次切断ans.next指向的地方在哪。这也是虚拟头技巧的底层依据——链表的指针操作本质是「引用指向」的修改理解了这一点虚拟头的作用就一目了然。虚拟头有两个作用将头节点变成中间节点简化判断头节点是最常见的边界。用一个虚拟头指向头节点后虚拟头成了新的头节点而虚拟头不是题目给的节点、不参与运算因此无需为头节点做特殊判断通过在合适的时候断开链接返回链表的中间节点新建一个虚拟头让它在恰当的时候刚好指向需要返回的节点断开连接最后返回虚拟头的 next即可。例如 25. K 个一组翻转链表 就用到了这个技巧——题解中dummy节点保持不变最终返回dummy.next见 25.reverse-nodes-in-k-groups.md。这一技巧同样适用于二叉树等问题例如「返回二叉树最左下节点」也可以用「虚拟节点跟随移动、到达目标时断开」的思路。技巧二快慢指针判断链表是否有环、以及环的入口都可以用快慢指针解决。仓库 142. 环形链表 II 给出了完整推导与多语言实现定义 fast 指针每次前进两步、slow 指针每次前进一步两指针第一次相遇时将 fast 指针重置到链表头部之后两指针都每次前进一步第二次相遇的节点即为环的入口。其数学依据见 142.Linked-List-Cycle-II.md设 A 为头节点到环入口的距离、B 为入口到第一次相遇点的距离、L 为环长第一次相遇时慢指针走了 s1 A B n1·L快指针走了 s2 A B n2·L且 s2 2·s1推导可得 A -B (n2 - n1)·L。由于整数圈的性质等价于「从第一次相遇点再向前走 A 步会到达环入口」。快慢指针法的时间复杂度为 O(N)、空间复杂度 O(1)。该题还提供了哈希表法遍历时用 Set 记录已访问节点第一个重复的节点即环入口时间复杂度 O(N)、空间复杂度 O(N)作为对比参考。快慢指针的另一大类应用是定位特定位置由于链表不支持随机访问找中间项、倒数第 N 项等需要特殊手段找链表中间项快指针一次走两步、慢指针一次走一步快指针走到头时慢指针刚好在中间找倒数第 N 个节点让快指针先走 N 步然后快慢指针同步前进快指针到头时慢指针正好是倒数第 N 个节点。61. 旋转链表 就是快慢指针的典型应用先求链表长度令k k % len右移 k 位与右移 k % len 效果相同如同 1000 米环形跑道跑 1100 米与 100 米到达同一地点再用快慢指针定位倒数第 N1 与倒数第 N 个节点将倒数第 N1 个节点的 next 置空、尾节点 next 指向 head返回倒数第 N 个节点即可见 61.Rotate-List.md。这类技巧属于「会了就容易、且不容易忘不会就难以想出」的类型练几道题即可掌握。技巧三穿针引线这是针对第二个考点——拼接链表——的专项技巧。作者在 25. K 个一组翻转链表、61. 旋转链表 和 92. 反转链表 II 中都用了这个方法。穿针引线通常不是最优解但好理解、方便书写、不易出错推荐新手使用。以「反转链表的中间一部分」为例对应 92. 反转链表 II即 m 到 n 区间反转反转部分已经用上文模板解决关键在于如何把反转好的子链表拼接回去从左到右给断点编号设两个断点涉及四个节点 a、b、c、d——a、d 分别是需要反转部分的前驱和后继不参与反转b、c 是需要反转部分的头和尾参与反转除了 cur 外多用两个指针 pre 和 next 即可定位 a、b、c、d定位后直接「穿针引线」a.next c b.next d这个「四点法」在 92.reverse-linked-list-ii.md 中被命名为「四点法」用 p1、p2、p3、p4 四个变量记录特殊节点然后操作这四个节点按一定方式连接同时注意 m 为 1 或 n 为链表长度等特殊情况——此时用虚拟节点 dummy 简化dummy.next head最终返回dummy.next并注意 p2.next 需置空以防互相引用造成无限循环见 92.reverse-linked-list-ii.md。25. K 个一组翻转链表 还给出了两个扩展练习一是从后往前以 k 个为一组翻转字节跳动面试题思路是先翻转整个链表、再按 k 分组翻转、最后再整体翻转回来二是直接用四点法思路思考 k 组翻转见 25.reverse-nodes-in-k-groups.md。技巧四先穿再排后判空这是最后一个技巧实操价值很大。回到反转链表的模板代码cur head pre None while cur ! tail: # 留下联系方式 next cur.next # 修改指针 cur.next pre # 继续往下走 pre cur cur next先穿先别管顺序先把所有修改指针的代码写出来包括反转的修改指针、穿针引线的修改指针。再排代码总量确定后再考虑顺序保证没有 bug。以上面两行为例必须先next cur.next再cur.next pre因为后一条语句执行后cur.next就变了若顺序颠倒链表会在此断开后面的节点全部访问不到。更一般的规律是只需考虑被修改了 next 指针的那部分代码比如cur.next pre改的是 cur 的 next后续凡是会用到cur.next的地方都要检查顺序其他代码无需逐一考虑。后判空同样代码总量确定后只需检查哪些行会空指针异常——仍然只需聚焦被改变 next 指针的部分。例如while cur: cur cur.nextcur不可能为空因为 while 条件已保证无需判空。而下面这段代码中的第二个 next 就需要判空while cur: next cur.next n_next next.next # next 可能为 null需判空修正为while cur: next cur.next if not next: break n_next next.next题目推荐用上述知识解决以下题目对应仓库中已收录题解的标注21. 合并两个有序链表删除排序链表中的重复元素 II若仓库已收录对应题解删除排序链表中的重复元素86. 分隔链表92. 反转链表 II复制带随机指针的链表环形链表142. 环形链表 II重排链表排序链表206. 反转链表回文链表总结数组与链表在逻辑上没有大的区别基本操作大同小异。单链表无法在 O(1) 时间内拿到前驱节点这是链表增删操作依赖前驱节点的本质特性也是遍历时总是要维护一个pre节点的根本原因。需要澄清一个可能的疑问「考点只有指针修改和链表拼接为什么我做题还要会用前缀和」——因为所有数据结构底层都是数组或链表本文讨论的是入参为链表、需要对链表做基本操作的题目如果题目需要归并排序去合并链表那归并排序本身已不在本专题讨论范围内。链表的考点聚焦于增删查的基本操作与复杂度。最后用口诀收束全文一个原则画图。能画出图、并根据图进行操作就入门了两个考点指针的修改典型是反转与链表的拼接——这是链表的精髓也是主要考点三个注意环、边界、前后序。环分「题目自带」90% 用快慢指针解决与「操作指针时产生」用画图 聚焦子结构解决边界问题中的头节点判断可用虚拟节点化解递归解法务必分清前序只思考子结构前面已处理与后序只思考子结构后面已处理推荐前序遍历因为它容易改造成不用栈的迭代写法四个技巧虚拟头把头节点变成中间节点、在合适时机断开返回中间节点、快慢指针判环/环入口/中间项/倒数第 N 项、穿针引线四点法拼接子链表、先穿再排后判空先写全指针修改再排顺序最后只对被改 next 的部分判空。以上内容以仓库 thinkings/linked-list.md 为骨架结合 problems 目录下的多篇链表题解源码如 92.reverse-linked-list-ii.md、25.reverse-nodes-in-k-groups.md、142.Linked-List-Cycle-II.md、61.Rotate-List.md交叉印证读者可进一步阅读仓库中 thinkings 目录下的其他专题如 thinkings/binary-tree-traversal.md、thinkings/basic-data-structure.md构建完整的算法知识体系。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
链表题解方法论：leetcode 仓库链表专题「一个原则、两个考点、三个注意、四个技巧」实战指南
链表题解方法论leetcode 仓库链表专题「一个原则、两个考点、三个注意、四个技巧」实战指南【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读链表是各类数据结构队列、栈、树、图在物理存储层最常见的底层形态之一也是 LeetCode 面试题中出现频率最高的专题之一。本文基于 leetcode 仓库 thinkings/linked-list.md 专题文档系统梳理链表的物理本质、基本操作与复杂度、数组对比以及作者提炼的解题口诀「一个原则、两个考点、三个注意、四个技巧」并结合仓库中 92. 反转链表 II、25. K 个一组翻转链表、142. 环形链表 II、61. 旋转链表 等题解源码帮助读者建立从原理到实战的完整链表解题框架。引言链表专题的整体图景链表在 LeetCode 的 linked list 标签下共有54 道题。作者在准备该专题时花数天时间将几乎全部链表题目刷完除六道加锁题目外并由此归纳出一个结论链表题的考点非常单一除设计类题目外本质上只考察两件事——指针的修改与链表的拼接。正因如此只要掌握了正确的方法论链表题并不难LeetCode 平台中链表标签下处于困难Hard难度的题目只有两道23. 合并 K 个升序链表基本没有复杂的链表操作用常规的归并排序即可解决核心前置是「合并两个有序链表」这一简单题25. K 个一组翻转链表即仓库中的 25.reverse-nodes-in-k-groups.md在掌握下文的反转子链表模板后可以轻松拿下。合并两个有序数组同样是简单题其难度与合并两个有序链表几乎一致。相关解法可参考 21.merge-two-sorted-lists.en.md。针对「指针绕来绕去就绕晕」「老是死循环」等常见痛点作者总结了六字口诀一个原则两个考点三个注意四个技巧。下文将逐项展开。链表基础从物理内存到逻辑结构数组与链表物理内存的两种使用方式各种数据结构——无论是队列、栈等线性结构还是树、图等非线性结构——从根本上讲底层都是数组和链表。物理内存由一个个大小相同的内存单元构成而数组和链表正是使用这些物理内存的两种不同方式数组占用连续的内存空间每个单元大小固定因此可以按下标随机访问但也因为空间紧密相连头部的插入和删除复杂度为 O(N)平均复杂度也是 O(N)只有尾部插入/删除为 O(1)。链表物理存储单元上非连续、非顺序数据元素的逻辑顺序通过节点中的指针链接次序实现链表的查找依赖 next 指针遍历因此不支持随机访问。一句话概括数组对查询友好、对增删不友好链表则相反。链表适合数据需要保持一定顺序、但又要频繁增删的场景。图 1 至图 3物理内存图、数组与链表物理存储对比图、链表逻辑表示图为作者绘制于专题文档中因仓库内无对应静态资源文件此处以文字描述代替图示读者可结合自绘示意图理解。单链表的定义与结构链表由一系列节点结点组成节点可在运行时动态生成。一个典型的单链表节点定义如下TypeScriptinterface ListNodeT { data: T; next: ListNodeT; }其中data是数据域存放数据next是指向下一个节点的指针后驱节点。若是双向链表还会有一个前驱节点pre。力扣平台通常使用如下 Java 类模拟链表节点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; } }一个有趣的视角链表其实就是特殊的树即「一叉树」。这也是链表天然具有递归性的原因后文的「前后序」部分会利用这一点。链表的基本操作与复杂度插入插入只需要考虑插入位置的前驱节点和后继节点双向链表还需要更新后继节点其他节点不受影响。因此在给定前驱节点指针的情况下插入的时间复杂度为 O(1)若未给定指针需先遍历查找节点最坏情况下为 O(N)。伪代码temp 待插入位置的前驱节点.next 待插入位置的前驱节点.next 待插入指针 待插入指针.next temp提示 1考虑头尾指针的情况提示 2新手推荐先画图再写代码熟练后可省略画图。删除删除只需将待删除节点的前驱节点的 next 指针修正为其下下个节点注意考虑边界条件。伪代码待删除位置的前驱节点.next 待删除位置的前驱节点.next.next遍历迭代伪代码当前指针 头指针 while 当前节点不为空 { print(当前节点) 当前指针 当前指针.next }前序遍历风格的递归伪代码dfs(cur) { if 当前节点为空 return print(cur.val) return dfs(cur.next) }数组与链表操作细节的「神相似」作者强调数组和链表同为线性结构二者在逻辑上有很多相似之处只是在细微操作和使用场景上有差异而使用场景在题目中很难直接考察。对比以下两段遍历代码// 数组遍历 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」。再看逆序遍历// 数组逆序遍历 for(int i arr.size() - 1; i -1; i--) { print(arr[i]) } // 链表逆序遍历需双向链表 for (ListNode cur tail; cur ! null; cur cur.pre) { print(cur.val) }单链表无法在 O(1) 时间内拿到前驱节点这也是为什么很多题解中需要自行维护一个前驱节点pre。向尾部追加元素push数组可以直接arr.push(1)底层近似为「扩容 尾部赋值」而链表没有内置的 push 方法需要自行实现// 假设 tail 是链表的尾部节点 tail.next new ListNode(lucifer) tail tail.next这两行代码执行后tail 依然指向尾部节点。这个技巧在复制链表、逐个拼接新节点时非常实用。作者特别提醒不建议把链表先转成数组再做这种做法等于否定了链表存在的价值。一个原则画图画图是贯穿所有链表题目的准则尤其对于新手无论简单题还是难题都要画图。画图的作用与打草稿、写备忘录同理把存在脑子里的东西放到纸上减少认知负担——可以把大脑比作 CPU、脑内记忆比作寄存器寄存器容量有限需要把不常用的信息放到「内存」纸、平板等一切可画图介质里。画得好不好看不重要能看清关系即可。两个考点考点一指针的修改指针修改最典型的代表就是链表反转。对数组这种支持随机访问的结构反转很容易头尾不断交换即可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; }而链表反转则麻烦得多力扣中反转类题目非常多。作者给出了一个可复用的任意一段链表反转模板# 翻转一个子链表并返回新的头与尾 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其中head是需要反转的头节点tail是需要反转的尾节点。若 head 是整个链表的头、tail 是整个链表的尾即反转整个链表否则就是反转局部链表。实现要点这也是画图价值的直接体现仅用cur.next pre一步修改指针会同时造成两个问题一是可能产生环导致死循环二是让链表「分道扬镳」。因此反转前必须先记录下一个节点next cur.next cur.next pre cur next关于环因为从前往后遍历时前面的链表已经被反转实际并不会成环图需要按正确的遍历顺序绘制。tail 本身没有被反转从上面的循环条件cur ! tail可见tail 并未参与反转。解决办法是把 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这个带terminal的版本正是 25. K 个一组翻转链表 Python 解法中reverse函数的原始模板——仓库题解中reverseKGroup每 k 个一组调用self.reverse(head, tail, tail.next)随后用pre.next head、tail.next next把子链表重新接回原链表见 25.reverse-nodes-in-k-groups.md。考点二链表的拼接链表题总喜欢「穿来穿去」拼接比如反转链表 II、合并有序链表等。这并非偶然而是链表的本质价值所在链表不必要求物理内存连续对插入和删除友好因此拼接类操作天然高频出现。掌握了上文的基本操作配合下文「穿针引线」技巧拼接类题目即可迎刃而解。三个注意链表题最容易出错的 90% 集中在以下三种情况环死循环、边界条件、递归前后序。注意一环环的考点有两类题目本身就有环让你判断是否有环以及环的位置——这类问题用「快慢指针」解决下文展开题目链表本来无环但操作指针时被「整出环」了——这是本文重点讨论的场景。避免出现环最有效的措施就是画图如果两个或几个节点构成了环通过图很容易看出来。实操技巧是先画图然后把对指针的每一次操作都反映到图中。由于链表是递归的数据结构很多链表问题如反转天生具有递归性只需画出其中一个子结构即可不需要画出整个链表。注意二边界很多人出错是没有考虑边界。考虑边界的一个技巧是仔细看题目信息如果题目的头节点可能被移除考虑使用虚拟节点这样头节点就变成了中间节点无需为头节点做特殊判断如果题目要求返回的不是原本的头节点而是尾部节点或其他中间节点要注意指针的变化。具体内容在「四个技巧」的虚拟头部分展开。注意三前后序链表结构天生具有递归性使用递归思维解题往往事半功倍。仓库的 thinkings/binary-tree-traversal.md 详细讲解了二叉树的前序、中序、后序三种遍历前中后序指的是当前节点相对子节点的处理顺序。而绝大多数链表题都是单链表只有一个后继指针因此只有前序和后序没有中序遍历。判断前序还是后序关键是看主逻辑改变指针的代码的位置主逻辑在进入子节点之前执行是前序在递归返回过程中执行是后序。以一个同时包含 pre/post 逻辑的代码为例def traverse(root): print(pre) traverse(root.left) traverse(root.righ) print(post)以反转链表为例前序遍历写法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两种写法的边界、入参、代码均不同。记忆口诀很简单前序遍历想象前面的链表都已经处理好了怎么处理的不必管只聚焦子结构此时前面的链表不会成环后面的链表还没处理因此需要通过next head.next留下联系方式后序遍历想象后面的链表都已经处理好了只聚焦子结构此时可以通过head.next.next head完成反转但会临时产生环因此需要将head.next置空如head.next None来防止环。后序遍历之所以要置空从图中可以非常直观地看出head.next.next head之后两个节点互相引用形成环置空head.next即可打破。推荐使用前序遍历前序遍历容易改造成不需要栈的迭代写法而后序遍历的主逻辑在函数调用栈的弹出过程必须借助栈完成。这一点可以从上文「迭代版反转」与「前序递归版反转」的对比中看出——两者的指针操作顺序完全一致。写递归的一个技巧想象自己已经处理好了部分数据并「用手挡起来」剩下的部分还没处理接下来思考「如何根据已处理的数据和当前数据推导出还未处理的数据」。四个技巧技巧一虚拟头dummy head先做三个小测验考察对指针引用关系的理解Q1如下代码ans.next指向什么ans ListNode(1) ans.next head head head.next head head.nextA1最开始的 headans.next指向的是被head head.next切断前的原 head 节点head的重新赋值不影响ans。Q2如下代码ans.next指向什么ans ListNode(1) head ans head.next ListNode(3) head.next ListNode(4)A2ListNode(4)head与ans仍指向同一对象head.next被连续修改为 ListNode(3)、ListNode(4)ans.next同步变化。Q3如下代码ans.next指向什么ans ListNode(1) head ans head.next ListNode(3) head ListNode(2) head.next ListNode(4)A3ListNode(3)关键在head ListNode(2)这一行它切断了head与ans的引用关系此后对head的一切操作都不再影响ans。核心规律ans.next指向什么取决于最后一次切断ans.next指向的地方在哪。这也是虚拟头技巧的底层依据——链表的指针操作本质是「引用指向」的修改理解了这一点虚拟头的作用就一目了然。虚拟头有两个作用将头节点变成中间节点简化判断头节点是最常见的边界。用一个虚拟头指向头节点后虚拟头成了新的头节点而虚拟头不是题目给的节点、不参与运算因此无需为头节点做特殊判断通过在合适的时候断开链接返回链表的中间节点新建一个虚拟头让它在恰当的时候刚好指向需要返回的节点断开连接最后返回虚拟头的 next即可。例如 25. K 个一组翻转链表 就用到了这个技巧——题解中dummy节点保持不变最终返回dummy.next见 25.reverse-nodes-in-k-groups.md。这一技巧同样适用于二叉树等问题例如「返回二叉树最左下节点」也可以用「虚拟节点跟随移动、到达目标时断开」的思路。技巧二快慢指针判断链表是否有环、以及环的入口都可以用快慢指针解决。仓库 142. 环形链表 II 给出了完整推导与多语言实现定义 fast 指针每次前进两步、slow 指针每次前进一步两指针第一次相遇时将 fast 指针重置到链表头部之后两指针都每次前进一步第二次相遇的节点即为环的入口。其数学依据见 142.Linked-List-Cycle-II.md设 A 为头节点到环入口的距离、B 为入口到第一次相遇点的距离、L 为环长第一次相遇时慢指针走了 s1 A B n1·L快指针走了 s2 A B n2·L且 s2 2·s1推导可得 A -B (n2 - n1)·L。由于整数圈的性质等价于「从第一次相遇点再向前走 A 步会到达环入口」。快慢指针法的时间复杂度为 O(N)、空间复杂度 O(1)。该题还提供了哈希表法遍历时用 Set 记录已访问节点第一个重复的节点即环入口时间复杂度 O(N)、空间复杂度 O(N)作为对比参考。快慢指针的另一大类应用是定位特定位置由于链表不支持随机访问找中间项、倒数第 N 项等需要特殊手段找链表中间项快指针一次走两步、慢指针一次走一步快指针走到头时慢指针刚好在中间找倒数第 N 个节点让快指针先走 N 步然后快慢指针同步前进快指针到头时慢指针正好是倒数第 N 个节点。61. 旋转链表 就是快慢指针的典型应用先求链表长度令k k % len右移 k 位与右移 k % len 效果相同如同 1000 米环形跑道跑 1100 米与 100 米到达同一地点再用快慢指针定位倒数第 N1 与倒数第 N 个节点将倒数第 N1 个节点的 next 置空、尾节点 next 指向 head返回倒数第 N 个节点即可见 61.Rotate-List.md。这类技巧属于「会了就容易、且不容易忘不会就难以想出」的类型练几道题即可掌握。技巧三穿针引线这是针对第二个考点——拼接链表——的专项技巧。作者在 25. K 个一组翻转链表、61. 旋转链表 和 92. 反转链表 II 中都用了这个方法。穿针引线通常不是最优解但好理解、方便书写、不易出错推荐新手使用。以「反转链表的中间一部分」为例对应 92. 反转链表 II即 m 到 n 区间反转反转部分已经用上文模板解决关键在于如何把反转好的子链表拼接回去从左到右给断点编号设两个断点涉及四个节点 a、b、c、d——a、d 分别是需要反转部分的前驱和后继不参与反转b、c 是需要反转部分的头和尾参与反转除了 cur 外多用两个指针 pre 和 next 即可定位 a、b、c、d定位后直接「穿针引线」a.next c b.next d这个「四点法」在 92.reverse-linked-list-ii.md 中被命名为「四点法」用 p1、p2、p3、p4 四个变量记录特殊节点然后操作这四个节点按一定方式连接同时注意 m 为 1 或 n 为链表长度等特殊情况——此时用虚拟节点 dummy 简化dummy.next head最终返回dummy.next并注意 p2.next 需置空以防互相引用造成无限循环见 92.reverse-linked-list-ii.md。25. K 个一组翻转链表 还给出了两个扩展练习一是从后往前以 k 个为一组翻转字节跳动面试题思路是先翻转整个链表、再按 k 分组翻转、最后再整体翻转回来二是直接用四点法思路思考 k 组翻转见 25.reverse-nodes-in-k-groups.md。技巧四先穿再排后判空这是最后一个技巧实操价值很大。回到反转链表的模板代码cur head pre None while cur ! tail: # 留下联系方式 next cur.next # 修改指针 cur.next pre # 继续往下走 pre cur cur next先穿先别管顺序先把所有修改指针的代码写出来包括反转的修改指针、穿针引线的修改指针。再排代码总量确定后再考虑顺序保证没有 bug。以上面两行为例必须先next cur.next再cur.next pre因为后一条语句执行后cur.next就变了若顺序颠倒链表会在此断开后面的节点全部访问不到。更一般的规律是只需考虑被修改了 next 指针的那部分代码比如cur.next pre改的是 cur 的 next后续凡是会用到cur.next的地方都要检查顺序其他代码无需逐一考虑。后判空同样代码总量确定后只需检查哪些行会空指针异常——仍然只需聚焦被改变 next 指针的部分。例如while cur: cur cur.nextcur不可能为空因为 while 条件已保证无需判空。而下面这段代码中的第二个 next 就需要判空while cur: next cur.next n_next next.next # next 可能为 null需判空修正为while cur: next cur.next if not next: break n_next next.next题目推荐用上述知识解决以下题目对应仓库中已收录题解的标注21. 合并两个有序链表删除排序链表中的重复元素 II若仓库已收录对应题解删除排序链表中的重复元素86. 分隔链表92. 反转链表 II复制带随机指针的链表环形链表142. 环形链表 II重排链表排序链表206. 反转链表回文链表总结数组与链表在逻辑上没有大的区别基本操作大同小异。单链表无法在 O(1) 时间内拿到前驱节点这是链表增删操作依赖前驱节点的本质特性也是遍历时总是要维护一个pre节点的根本原因。需要澄清一个可能的疑问「考点只有指针修改和链表拼接为什么我做题还要会用前缀和」——因为所有数据结构底层都是数组或链表本文讨论的是入参为链表、需要对链表做基本操作的题目如果题目需要归并排序去合并链表那归并排序本身已不在本专题讨论范围内。链表的考点聚焦于增删查的基本操作与复杂度。最后用口诀收束全文一个原则画图。能画出图、并根据图进行操作就入门了两个考点指针的修改典型是反转与链表的拼接——这是链表的精髓也是主要考点三个注意环、边界、前后序。环分「题目自带」90% 用快慢指针解决与「操作指针时产生」用画图 聚焦子结构解决边界问题中的头节点判断可用虚拟节点化解递归解法务必分清前序只思考子结构前面已处理与后序只思考子结构后面已处理推荐前序遍历因为它容易改造成不用栈的迭代写法四个技巧虚拟头把头节点变成中间节点、在合适时机断开返回中间节点、快慢指针判环/环入口/中间项/倒数第 N 项、穿针引线四点法拼接子链表、先穿再排后判空先写全指针修改再排顺序最后只对被改 next 的部分判空。以上内容以仓库 thinkings/linked-list.md 为骨架结合 problems 目录下的多篇链表题解源码如 92.reverse-linked-list-ii.md、25.reverse-nodes-in-k-groups.md、142.Linked-List-Cycle-II.md、61.Rotate-List.md交叉印证读者可进一步阅读仓库中 thinkings 目录下的其他专题如 thinkings/binary-tree-traversal.md、thinkings/basic-data-structure.md构建完整的算法知识体系。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考