链表题解方法论：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（物理内存图、数组与链表物理存储对比图、链表逻辑表示图）为作者绘制于专题文档中，因仓库内无对应静态资源文件，此处以文字描述代替图示，读者可结合自绘示意图理解。

单链表的定义与结构

链表由一系列节点（结点）组成，节点可在运行时动态生成。一个典型的单链表节点定义如下（TypeScript）：

interface ListNode<T> { data: T; next: ListNode<T>; }

其中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 是整个链表的尾，即反转整个链表；否则就是反转局部链表。

实现要点（这也是画图价值的直接体现）：

1. 仅用cur.next = pre一步修改指针，会同时造成两个问题：一是可能产生环导致死循环；二是让链表「分道扬镳」。因此反转前必须先记录下一个节点：

next = cur.next cur.next = pre cur = next

2. 关于环：因为从前往后遍历时，前面的链表已经被反转，实际并不会成环，图需要按正确的遍历顺序绘制。
3. 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% 集中在以下三种情况：环（死循环）、边界条件、递归（前后序）。

注意一：环

环的考点有两类：

1. 题目本身就有环，让你判断是否有环以及环的位置——这类问题用「快慢指针」解决，下文展开；
2. 题目链表本来无环，但操作指针时被「整出环」了——这是本文重点讨论的场景。

避免出现环最有效的措施就是画图：如果两个或几个节点构成了环，通过图很容易看出来。实操技巧是：先画图，然后把对指针的每一次操作都反映到图中。由于链表是递归的数据结构，很多链表问题（如反转）天生具有递归性，只需画出其中一个子结构即可，不需要画出整个链表。

注意二：边界

很多人出错是没有考虑边界。考虑边界的一个技巧是仔细看题目信息：

• 如果题目的头节点可能被移除，考虑使用虚拟节点，这样头节点就变成了中间节点，无需为头节点做特殊判断；
• 如果题目要求返回的不是原本的头节点，而是尾部节点或其他中间节点，要注意指针的变化。

具体内容在「四个技巧」的虚拟头部分展开。

注意三：前后序

链表结构天生具有递归性，使用递归思维解题往往事半功倍。仓库的 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.next

A1：最开始的 head（ans.next指向的是被head = head.next切断前的原 head 节点，head的重新赋值不影响ans）。

Q2：如下代码ans.next指向什么？

ans = ListNode(1) head = ans head.next = ListNode(3) head.next = ListNode(4)

A2：ListNode(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)

A3：ListNode(3)（关键在head = ListNode(2)这一行，它切断了head与ans的引用关系，此后对head的一切操作都不再影响ans）。

核心规律：ans.next指向什么，取决于最后一次切断ans.next指向的地方在哪。这也是虚拟头技巧的底层依据——链表的指针操作本质是「引用指向」的修改，理解了这一点，虚拟头的作用就一目了然。虚拟头有两个作用：

1. 将头节点变成中间节点，简化判断：头节点是最常见的边界。用一个虚拟头指向头节点后，虚拟头成了新的头节点，而虚拟头不是题目给的节点、不参与运算，因此无需为头节点做特殊判断；
2. 通过在合适的时候断开链接，返回链表的中间节点：新建一个虚拟头，让它在恰当的时候（刚好指向需要返回的节点）断开连接，最后返回虚拟头的 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 米到达同一地点）；再用快慢指针定位倒数第 N+1 与倒数第 N 个节点，将倒数第 N+1 个节点的 next 置空、尾节点 next 指向 head，返回倒数第 N 个节点即可（见 61.Rotate-List.md）。

这类技巧属于「会了就容易、且不容易忘，不会就难以想出」的类型，练几道题即可掌握。

技巧三：穿针引线

这是针对第二个考点——拼接链表——的专项技巧。作者在 25. K 个一组翻转链表、61. 旋转链表 和 92. 反转链表 II 中都用了这个方法。穿针引线通常不是最优解，但好理解、方便书写、不易出错，推荐新手使用。

以「反转链表的中间一部分」为例（对应 92. 反转链表 II，即 m 到 n 区间反转）：

1. 反转部分已经用上文模板解决，关键在于如何把反转好的子链表拼接回去；
2. 从左到右给断点编号：设两个断点涉及四个节点 a、b、c、d——a、d 分别是需要反转部分的前驱和后继（不参与反转），b、c 是需要反转部分的头和尾（参与反转）；
3. 除了 cur 外，多用两个指针 pre 和 next 即可定位 a、b、c、d；
4. 定位后直接「穿针引线」：

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.next

cur不可能为空，因为 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. 合并两个有序链表
• 82. 删除排序链表中的重复元素 II（若仓库已收录对应题解）
• 83. 删除排序链表中的重复元素
• 86. 分隔链表
• 92. 反转链表 II
• 138. 复制带随机指针的链表
• 141. 环形链表
• 142. 环形链表 II
• 143. 重排链表
• 148. 排序链表
• 206. 反转链表
• 234. 回文链表

总结

数组与链表在逻辑上没有大的区别，基本操作大同小异。单链表无法在 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