最近在整理自己的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 快慢指针的应用场景矩阵快慢指针不止能判环它在链表题里是个通用工具。我把最常用的场景整理成了一张表场景思路典型题目判断是否有环快慢指针是否相遇环形链表寻找环的入口相遇后某个指针重置到头再同步走环形链表II找到链表中点快指针到末尾时慢指针在中点排序链表/回文链表找倒数第K个节点快指针先走K步再两个同时走删除倒数第N个节点判断回文链表先找中点再反转后半段回文链表寻找环入口的推导值得展开说一下。设链表头到环入口的距离为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大多集中在指针操作和边界条件上我在刷题过程中整理了一份高频错误清单错误类型现象原因访问空指针运行时报错没有判断cur或cur.next是否为空链表成环程序超时修改指针前没有保存后继节点头结点丢失返回结果少了一截直接操作了头结点没有使用虚拟头结点指针移动错误结果顺序不对循环体内忘了更新某一指针递归溢出栈溢出递归边界条件写错或递归层数过多所有错误里链表成环是后果最严重的因为本地调试时程序会一直运行表面上看起来像死循环实际是链表被改成了环遍历永远无法到达末尾。最常见的形成原因就是反转链表时没有先保存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指到的位置比预期早了一个节点导致返回的头结点错了用这个方法一眼就找到了问题。链表篇不难但需要耐心和细心每个隐患都有自己的规律多写、多复盘这个专题很快就能变成你刷题列表里最有底气的部分。