LeetCode链表题全攻略：从虚拟头结点到快慢指针的通用解法

最近在整理自己的LeetCode刷题笔记，链表这一章给了我不少感触。很多人刚开始刷题时，把链表当成“送分题”，结果一到手写环节就翻车——不是空指针异常，就是链表被改成了环，甚至在一个反转操作上卡了半小时。链表确实是数据结构里最基础的内容之一，但正因为基础，面试官才特别爱拿它来检验候选人的指针功底和边界意识。这篇内容想写给准备技术面试的朋友，也写给那些刷题刷到链表就头疼的人。我会从问题拆解、核心套路、常见Bug排查到刷题路线，把LeetCode链表篇里的典型题目和通用解法一次性讲明白。

1. 链表题的系统认知与准备路线

1.1 为什么链表题值得单独开一篇

链表和数组最大的区别在于存储方式。数组是连续内存，按下标访问是O(1)；链表是离散节点，每个节点存着指向下一个节点的引用，访问某个位置必须从头遍历，复杂度是O(n)。但链表也有自己的优势：在已知前驱节点的情况下，插入和删除操作的时间复杂度是O(1)，不需要像数组那样搬移大量元素。

LeetCode上的链表题，表面看是考数据结构，实际上考的是三件事：一是对指针引用的掌控力，二是对边界条件的敏感度，三是递归和迭代两种思维模式的切换能力。我见过不少人能把动态规划题讲得头头是道，却在“删除倒数第N个节点”这种题上写不出一份没有Bug的代码，原因就是链表题需要高度精确的“指针操作直觉”，这种直觉只能靠专项训练获得。

从题型分布来看，链表题大致可以分成三类：基础操作类（反转、合并、删除、查找）、经典算法类（环检测、相交判断、回文判断）、综合建模类（复制带随机指针链表、K个一组翻转、排序链表）。大多数人会做的通常只是第一类的简单版本，一旦进入第二类和第三类，就需要把多个技巧组合起来使用。所以我觉得，链表篇值得单独开一篇笔记，把所有高频考点的通用解法串成一条线。

1.2 链表题的考试重点与学什么

我刷完链表篇后复盘，总结出四个必须吃透的核心技巧：虚拟头结点（哑节点）、快慢指针、双指针/三指针操作、递归与迭代的相互转化。这几个技巧可以覆盖链表题里八成以上的场景。

虚拟头结点解决的是“头结点没有前驱”的问题，它让删除节点、合并链表这类操作不需要单独处理头结点的特殊情况。快慢指针解决的是环检测、找中点、找倒数第K个节点这类需要定位的问题。双指针和三指针主要用在反转链表以及各种需要重排引用的操作中。递归则用来处理带有嵌套结构的问题，比如K个一组翻转、两两交换节点，这类题用递归写起来逻辑特别清晰，但理解门槛也高。

我在刷题前给自己定了一个标准：每道题先想清楚能不能用迭代写，再想递归怎么写，最后比较两种写法的可读性和空间复杂度。链表题的空间复杂度往往被忽略，很多人用递归解决反转链表，递归栈会带来O(n)的额外空间，面试官追问“能不能做到O(1)空间”时，如果只会递归写法就尴尬了。所以每个技巧我都要求自己至少准备一套迭代方案。

2. 虚拟头结点：所有删除类题目的万能钥匙

2.1 哑节点到底解决什么问题

链表题里最烦人的情况之一，就是操作对象恰好是头结点。比如删除链表中某个值为x的节点，如果这个节点是头结点，那删除后整个链表的头就变了。如果不做特殊处理，代码里会多出很多if (head.val == x) head = head.next之类的判断，写起来啰嗦，还容易漏分支。

虚拟头结点的思路非常简单：在真正的头结点前面额外造一个节点，这个节点不存储实际数据，它的next指向链表原来的头结点。之后所有遍历和删除操作都从虚拟头结点开始，到最后返回dummy.next作为新的头结点。这样一来，头结点和其他普通节点在逻辑上不再有区别，所有节点的删除、插入操作都能用一套统一的代码完成。

我打个比方，这就像隧道入口前的引导车，真正的车队第一辆不需要自己找入口，引导车先进入隧道，后续车辆跟着走就行了。虚拟头结点就是那辆引导车，它把“谁是第一位”的逻辑从算法里抽走，让代码专注于核心的指针操作，不用再操心特殊分支。

2.2 虚拟头结点的标准写法与内存注意点

虚拟头结点的标准写法很固定：

def delete_node(head, target): dummy = ListNode(0) dummy.next = head cur = dummy while cur.next: if cur.next.val == target: cur.next = cur.next.next else: cur = cur.next return dummy.next

这个写法的核心套路是：始终让cur停留在目标节点的前一个位置，通过修改cur.next的指向来删除目标节点。循环终止条件是cur.next不为空，删除后不移动cur，这样才能继续检查新接上来的节点是否也需要删除。全程没有对头结点的特殊判断，逻辑非常统一。

我只讲三个注意点。第一，如果用的是C或C++，删除节点后要记得手动释放内存，但在LeetCode的评测环境下一般不要求释放，面试时主动提一句“这里应该释放原节点的内存”会给面试官留下好印象。第二，Python和Java里不需要关心内存释放，但要避免让被删除后的节点还被局部变量引用，以免妨碍垃圾回收。第三，返回的是dummy.next而不是dummy本身，这是一个非常蠢但非常常见的错误，如果直接返回dummy，链表前面就多了一个值为0的节点，导致整个答案错误。

3. 快慢指针：环检测与链表中点的完整推导

3.1 为什么快指针一次走两步

快慢指针最常见的应用是判断链表是否有环，也就是Floyd判圈算法。慢指针每次走一步，快指针每次走两步，同时从head出发，如果链表存在环，两个指针最终一定会在环内相遇。这个结论看起来简单，但我见过不少人表示不理解：万一快指针直接跳过慢指针怎么办？

实际上在链表上不会发生“跳过”。因为每次移动一格，两个指针之间的距离要么是0，要么是1，当快指针在环内相对慢指针的速度是1时，它们的距离总会在某一刻变成0。可以把这个过程想象成两辆火车在同一条环形轨道上行驶，快车比慢车每小时多跑1公里，不管初始距离有多远，快车总会追上慢车，不存在跳过的概念。

这个算法的时间复杂度是O(n)，空间复杂度是O(1)，比用哈希集合记录访问过的节点要省空间得多。面试时如果遇到“判断链表是否有环”的题目，哈希集合的解法可以作为思路提一下，但最终一定要能写出快慢指针的版本。

3.2 快慢指针的应用场景矩阵

快慢指针不止能判环，它在链表题里是个通用工具。我把最常用的场景整理成了一张表：

寻找环入口的推导值得展开说一下。设链表头到环入口的距离为a，环的周长为b，两个指针相遇时慢指针走了a + m，其中m是入口到相遇点的距离。因为快指针速度是慢指针的两倍，快指针走了2(a + m)。同时快指针在环内额外走了若干圈，所以2(a + m) = a + m + n*b，即a + m = n*b。也就是说，慢指针从相遇点再往前走到环入口的距离，正好等于头部到环入口的距离。因此，相遇后把一个指针重置到头部，另一个留在相遇点，两个指针都每次走一步，它们再次相遇的位置就是环入口。

这个推导过程我在面试时被问过不止一次，建议每个人都能手推一遍，只记结论容易忘，能够自己推导出来才算真正掌握。

4. 高频题型拆解：反转与合并的三种写法

4.1 反转链表为什么总是写错

反转链表算是LeetCode链表篇最经典的入门题，也是很多人第一次“写出Bug但找不到原因”的题。反转的核心逻辑并不难：把每个节点的next指向前一个节点。但实际操作时，如果改完cur.next后再去取cur.next取到的就是前一个节点，整个遍历直接断裂。

我用迭代法举一下标准写法：

def reverse_list(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

这里最关键的是循环内的第一行代码：先把cur.next保存到nxt里，再修改cur.next的指向。如果不保存就直接改，原链表的后半段就丢了，循环也没办法继续下去。这个“先保存后继再修改指针”的习惯，是所有链表指针操作的基础，比反转本身的逻辑更值得内化。

递归写法看起来更简洁，但理解成本更高：

def reverse_list_recursive(head): if not head or not head.next: return head new_head = reverse_list_recursive(head.next) head.next.next = head head.next = None return new_head

这段代码的含义是：先反转从head.next开始的子链表，反转后的子链表头就是整个链表的头，再把原链表的头head接到末尾。关键在于head.next.next = head这一句，它让原来的后继节点反过来指向当前节点。递归逻辑的退出边界是“当前节点为空或只有一个节点”，此时不需要反转。

4.2 合并链表和区间反转的套路

合并两个有序链表是另一个高频题。迭代写法依然用到虚拟头结点：用dummy开头游走指针cur，每次比较两个链表的当前节点值，把较小的接到cur.next，然后移动对应链表的指针。循环结束后，把还剩下的一条链表直接接到末尾，返回dummy.next。

区间反转，比如反转从第m个节点到第n个节点之间的部分，比整链反转稍微复杂一点。我常用的思路是先找到第m-1个节点，把它记为pre，然后从pre.next开始做两次以上的局部反转操作。这里有个很经典的“逐个移动头插法”：每次把当前处理节点移动到区间头部，重复n-m次。这个写法的好处是代码量少，但指针移动很容易乱，需要画图配合才能保证不写错。

我在写这类题时有个习惯：把链表先画成一串盒子，每次修改指针前先在纸上标出哪些引用需要保存，哪些可以丢弃。链表题的几乎所有Bug都源于对引用的误判，画图能救回一大半。

5. 进阶专项：删除、复制、排序的综合解法

5.1 删除类变体：倒数第N个节点与重复元素

删除倒数第N个节点是快慢指针和哨兵节点的经典组合题。先用一个虚拟头结点，快指针先走N步，然后快慢指针同步前进，当快指针到达链表末尾时，慢指针正好停在倒数第N个节点的前一个位置，此时把slow.next = slow.next.next就完成了删除。

注意题目如果要求删除倒数第1个节点，也就是最后一个节点，这时候快指针先走N步后可能已经走过头，需要相应的边界判断。我在实际写这道题时踩过一个非常隐蔽的坑：如果没有虚拟头结点，当链表长度恰好为N，也就是要删除头结点时，慢指针会停在虚拟头结点而不是头结点的前驱，代码逻辑完全不同。所以这类题我一律使用虚拟头结点，统一所有分支。

删除排序链表中的重复元素有两种情况。一种是保留一个重复元素，比如1 -> 2 -> 2 -> 3变成1 -> 2 -> 3，这种比较简单，用cur.next和cur比较即可。另一种是重复元素全部删除，比如1 -> 2 -> 2 -> 3变成1 -> 3，这种需要额外关心“这个节点是否重复”的状态，并且在删除时要注意找到重复段的前驱。两种变体在面试中出现的概率都很高，建议分别刷一遍，别只记一种。

5.2 复制带随机指针链表：两种解法的取舍

复制带随机指针的链表是综合建模类的代表题。它的难点在于：每个节点除了next指针，还有一个random指针可以指向链表中任意节点，复制时必须保持这种随机引用关系。

最朴素的解法用哈希表：第一遍遍历原链表，为每个原节点创建一个新节点，并用哈希表记录映射关系；第二遍遍历时，根据原节点的next和random指向，从哈希表中取出对应的新节点来拼接。这个写法清晰易懂，时间复杂度O(n)，空间复杂度O(n)，适合面试时先给出这个保底方案。

进阶的无额外空间解法很巧妙，一共三步：第一步，在每个原节点后面复制一个相同的节点，让链表变成原节点1 -> 新节点1 -> 原节点2 -> 新节点2 -> ...；第二步，遍历链表，为每个新节点设置random指针，新节点的random就是原节点random的下一个节点；第三步，把交错链表拆成两条独立的链表，原链表保持不变，新链表作为结果返回。

这个解法省掉了哈希表，空间复杂度降到O(1)，但代码实现比哈希表复杂许多，尤其第三步拆分时的前后指针交替移动，非常容易在边界处出问题。我的建议是：两种解法都要能写出来，哈希表写快一点，O(1)空间版写稳一点。

5.3 排序链表：用归并还是用插入

排序链表是链表篇里综合度最高的一道题，它把找中点、合并有序链表、递归这三件事串在一起。对链表做归并排序，时间复杂度是O(n log n)，空间复杂度如果用递归实现是O(log n)的栈空间，因为递归最多log n层。

链表的归并排序和数组的归并排序最大的不同在于“分”的步骤。数组可以直接按下标取中点，链表必须通过快慢指针找到中点并截断成两条子链表，然后递归排序，最后用合并有序链表的逻辑把子链表合并起来。终止条件是链表为空或只有一个节点。

如果用自底向上的归并排序，也就是按步长step从1开始，两两归并，再让step翻倍，直到整个链表有序，可以把空间复杂度降到O(1)。这种写法需要用循环模拟递归，期间要仔细维护每一段的头尾指针，代码量会比递归版本多出不少。面试时如果没主动要求优化空间，用递归版本的归并排序已经足够；如果对方追问能否做到O(1)空间，再拿出自底向上的写法。

插入排序的链表版本则适合当成一道独立的题来练习，它的时间复杂度是O(n^2)，在面试中一般不会作为排序链表的最优解出现，但用来锻炼“在已排序链表中插入新节点”的基本功还不错。

6. 常见Bug与调试经验实录

6.1 链表题的高频错误清单

链表题的Bug大多集中在指针操作和边界条件上，我在刷题过程中整理了一份高频错误清单：

所有错误里，链表成环是后果最严重的，因为本地调试时程序会一直运行，表面上看起来像死循环，实际是链表被改成了环，遍历永远无法到达末尾。最常见的形成原因就是反转链表时没有先保存next就修改了cur.next，或者合并链表时把同一个节点的指针接到了之前的节点上。

空指针问题在删除类的题目中最常见，尤其是“删除倒数第N个节点”这种需要快慢指针配合的题目，稍不注意就会在快指针走完N步后访问fast.next。我的经验是，每次访问一个节点字段之前，先确认这个节点本身不为空。也可以在代码里用一个很短的断言或者手动模拟，几段关键代码可以用纸笔走两遍再提交。

6.2 我平时怎么调试链表题

链表题和普通数组题在调试上最大的不同是，链表结构不好直接观察。我常用的调试工具是一个打印链表的小函数：

def print_list(head): res = [] cur = head visited = 0 while cur and visited < 20: res.append(cur.val) cur = cur.next visited += 1 print(res)

注意我加了一个visited < 20的限制，这是为了防止链表意外成环时打印函数本身陷入死循环。调试时如果打印结果出现重复的元素或者长度始终是20，基本可以断定有环了。

另一个非常实用的技巧是“小样本用例测试”，每次写完链表题不要直接提交，先用五个固定用例在本地过一遍：空链表、只有一个节点、两个节点、删除头结点、删除尾结点。这五个用例能覆盖链表题八成以上的边界问题，实测下来比盲改代码效率高很多。很多新人刷题时只跑LeetCode给的示例，示例过完就提交，遇到隐藏的边界用例就挂掉，其实就是少了这个小样本自测的步骤。

7. 刷题顺序与三轮复习法

7.1 从易到难的刷题清单

链表篇的题目我建议按下面这个顺序刷，每个阶段都有明确的能力目标，不要一口气从简单跳到最难的题，容易劝退。

第一阶段是熟悉基础操作：反转链表、合并两个有序链表、删除链表中的节点、删除链表的倒数第N个节点、两两交换链表中的节点、环形链表，这几道题练的是虚拟头结点和双指针的基本功。第二阶段是综合运用：环形链表II、相交链表、回文链表、反转链表II、删除排序链表中的重复元素II，这一阶段要把多个技巧叠加起来。第三阶段是冲击难题：K个一组翻转链表、复制带随机指针的链表、排序链表，这三道题能顺利做出来，链表篇基本就过关了。

我个人不太建议按题的编号顺序刷，因为LeetCode的编号是固定的，难度并不完全递增。用专题的方式刷题，才能在短时间里形成对某种套路的感觉，而不是东碰一下西碰一下。

7.2 三轮复习的节奏控制

第一轮的目标是“听懂加能写”，遇到不会的题不要死磕超过半小时，直接看题解，看懂后合上题解重写一遍。写完后再对照题解思考不同写法的优缺点。第二轮的目标是“限时独立完成”，每道简单题控制在10分钟，中等题控制在25分钟，难题控制在40分钟以内，超时就标记出来，本轮结束时统一复盘。第三轮是随机抽查，从之前刷过的题里随机抽10道，不看题解直接写，重点看自己有没有把解法忘掉。

我自己的体会是第一轮刷一遍远远不够，很多题目当时看懂了，两周后就只剩模糊的印象。所以我把链表题的复习周期拉长到一个月，第一周专项突破，后续每周挑一天重刷之前的题，保持手感。链表这种题很吃“肌肉记忆”，一段时间不写，很多边界细节就会生疏，所以定期回炉是很有必要的。

8. 写在最后的一些个人体会

链表题的“手感”其实是可以刻意练习出来的。我一开始刷反转链表时，每写一步都要停下来想“现在的指针指向哪里”，写完整道题要花半小时还要改好几遍。刷了二十几道题之后，链表题的正确率明显上来了，原因不是我这段时间变聪明了，而是反复接触同一套模式后，大脑开始自动识别“这种题要用虚拟头结点”“这种题要用快慢指针”，这种模式识别能力就是手感。

最后分享一个我私藏的查错技巧：写完链表题之后，先把返回值之外的局部变量全部列出来，逐个检查它们从头到尾的指向变化是否合理。比如反转链表里prev、cur、nxt这三个变量在循环结束时分别指向哪个节点，如果能一口气说出来，这道题基本不会错。我之前踩过一次坑，循环结束后prev指到的位置比预期早了一个节点，导致返回的头结点错了，用这个方法一眼就找到了问题。链表篇不难，但需要耐心和细心，每个隐患都有自己的规律，多写、多复盘，这个专题很快就能变成你刷题列表里最有底气的部分。