链表是数据结构里绕不开的一道坎。很多人一开始觉得数组挺好用的一到链表就蒙圈尤其 OJ 题明明思路都对一提交就是一堆红叉。这篇文章是链表系列的第二篇专门聊 OJ 题。我会把链表题里最常见的考点、最容易踩的坑还有我自己刷题时总结的调试方法一次性讲清楚。你要是正准备考研数据结构、期末考或者刷力扣这篇文章应该能帮你少走不少弯路。1. 链表OJ的核心考点与整体思路1.1 链表节点的定义与内存模型先统一一下语言。刷题的时候链表节点最常见的定义是这样的用 C 语言写就是struct ListNode { int val; struct ListNode *next; };用 C 往往写成一个类力扣LeetCode里叫ListNode带构造函数用 Java 则是public class ListNode { int val; ListNode next; }。不管语言怎么变核心就两个字段数据域val和指针域next。我考研那会儿用的是王道、天勤的书代码基本都是这种结构体所以你别看平台不同底子是一样的。内存模型上链表和数组最大的区别就是数组是连续内存链表是零散内存靠指针串起来。这带来一个直接后果——你不能通过下标访问第 n 个节点必须从头往后走一遍。很多 OJ 题考的就是这个过程比如输出链表第 k 个节点、求链表长度都要求你用遍历的方式去做。1.2 链表题为什么容易卡人我总结了三个原因你对照一下自己是不是也这样第一指针理解不透。C/C 里p-next q和q p-next顺序搞反链表就直接断了或者形成一个环。很多初学者看到报错根本不知道问题出在哪一步。第二边界条件漏掉。比如链表为空、只有一个节点、删除尾节点、反转后新头变成了尾节点这些情况没处理好OJ 就会给你一个 Wrong Answer 或者 Runtime Error。第三不画图硬想。链表操作本来就是一个动态过程在脑子里纯想很容易绕晕。我见过太多同学在草稿纸上画画几分钟就写出来了空想半小时还做不对。所以我的建议是拿到一道链表 OJ 题先别急着写代码把链表在纸上画出来用一个简单例子比如 1-2-3-4走一遍过程再动手。这一点怎么强调都不过分。2. 高频链表OJ题型拆解与实操2.1 反转链表迭代法与递归法反转链表是最经典的题目没有之一。考研、面试、期末几乎必考。题目一般长这样给你单链表的头节点head请你反转链表并返回反转后的链表头节点。迭代法的核心是三个指针prev、cur、next。我们从头开始遍历每一步把当前节点的next指向前一个节点然后三个指针整体后移。代码模板如下struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *cur head; while (cur ! NULL) { struct ListNode *nextNode cur-next; // 先保存下一个节点否则断链 cur-next prev; // 反转指针 prev cur; // 前驱后移 cur nextNode; // 当前节点后移 } return prev; // 新的头节点 }这里有一个新手最容易写错的点cur-next prev执行之前必须先把cur-next保存下来否则cur原来的下一个节点就找不到了后面的链表全丢。我见过太多次Runtime Error: member access within null pointer就是因为这里没保存。递归法也很常问理解它能帮你加深对函数调用栈的认识struct ListNode* reverseList(struct ListNode* head) { if (head NULL || head-next NULL) return head; struct ListNode* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }递归法的核心在于先反转后面的链表然后让原来的下一个节点指向自己自己再指向空。这里的关键就是head-next-next head这一句不要写成head-next head那就变成自己指自己了俗称自环结果要么栈溢出要么死循环。2.2 寻找中间节点与倒数第K个节点这两道题经常成对出现因为它们都考察同样的思路快慢指针。找中间节点用slow一次走一步fast一次走两步。当fast走到链表末尾时slow正好在中间。对于偶数长度的链表中间节点通常取靠右的那个即第 n/2 1 个。力扣 876 题就是标准题。struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }注意循环条件里的fast ! NULL fast-next ! NULL顺序不能反。如果写fast-next ! NULL fast ! NULL当fast NULL时fast-next会先访问空指针直接崩溃。OJ 跑的时候会给你报 AddressSanitizer 或者 segment fault我一开始也踩过这个坑。找倒数第 K 个节点也是一样的快慢指针快指针先走 K 步然后两个指针一起走当快指针走到 NULL 时慢指针停的地方就是倒数第 K 个节点。这个思路比“先求长度再走 n-k 步”高效一些而且更优雅。代码我就不贴了你自己试着写一遍重点体会“间距固定为 K”这个思想。2.3 环形链表的检测与寻找入环节点环形链表这类题属于“你知道思路就简单不知道思路就一头雾水”的类型。判断链表有没有环用快慢指针快指针每次走两步慢指针每次走一步。如果没有环快指针会先碰到 NULL如果有环快指针和慢指针最终会在环里相遇。bool hasCycle(struct ListNode *head) { struct ListNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }这里有个细节快指针步长设为 2 是最合理的。如果设成 3、4两个指针可能在环里跳过对方虽然数学上最终也可能追上但实现和证明都变复杂了没必要。进阶版是找环的入口节点力扣 142 题。解法分两步先用快慢指针判断有环并找到相遇点然后把慢指针放回起点快指针也变成一步走两个指针再次相遇的位置就是环的入口。这个结论背后有数学推导我这里直接告诉你结论刷题阶段记住结论够用但考研复试被问到的话你要能推导一遍。2.4 合并两个有序链表与删除指定元素合并两个升序链表是另一座大山。思路很简单比较两个链头谁小取谁然后递归处理剩下的。迭代写法需要一个虚拟头节点dummy node这样能省去判断谁是最终头节点的麻烦。struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; // 栈上虚拟头节点也可以用 malloc 分配 dummy.next NULL; struct ListNode* tail dummy; while (list1 ! NULL list2 ! NULL) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } tail-next (list1 ! NULL) ? list1 : list2; return dummy.next; }虚拟头节点这个技巧非常实用它可以避免写一堆“如果头节点为空”之类的分支。以后你会发现很多链表题的简化都靠它。另外学会合并两个有序链表之后合并 K 个有序链表就是对这个代码的重复利用配合分治或优先队列那又是进阶题了。删除链表中等于给定值的所有节点力扣 203 题也很常考。同样可以用虚拟头节点然后遍历遇到值匹配的就跳过不匹配就接上。关键点在于删除后要记得释放内存考试或者 OJ 里虽然不检测内存泄漏但你自己写工程代码时必须养成好习惯。3. 链表OJ的常见陷阱与排查技巧3.1 四个最经典的Bug断链、自环、空指针、尾节点丢失我把链表题的易错点总结成四大类你在写代码的时候逐条自查Bug类型表现原因解决办法断链遍历到一半 next 变成垃圾地址修改 next 前没有保存后继先保存后继节点再改 next自环程序陷入死循环或内存暴增把 next 指向了自身或前面的节点画图确认每个 next 的指向空指针OJ 报 Runtime Error对 NULL 节点取 next 或 val循环条件加判空且顺序正确尾节点丢失反转或删除后链表尾部没有置 NULL新尾节点的 next 忘记赋 NULL操作结束后检查 tail-next举个自环的例子有人在反转链表时只有cur-next prev没有在最后prev-next上补 NULL结果新的尾节点还指向原来的下一个节点链节就乱套了。所以每道题写完第一件是拿一个长度为 1 的链表和长度为 2 的链表手动走一遍确认头尾指针都正确。3.2 用调试器和可视化工具快速定位问题很多人刷 OJ 时不太会用调试器只会在代码里加printf打印节点值。其实对于链表这种动态结构打印节点值往往看不出指针关系。我建议你用好以下工具本地 IDE 的断点调试在每次修改 next 的地方打断点观察变量的值配合单步执行看链表变化。伪可视化打印写一个辅助函数循环遍历打印链表比如1 - 2 - 3 - NULL每次改变后就打印一次能直观看到结构。画图这是最朴素也最有效的。哪怕是在纸上画我也建议你养成习惯。我自己刷题时会写一个printList函数测试用例全部用它验证。特别是出现死循环时打印到某个节点重复出现基本就能断定是成环了。除此之外在本地测试时故意构造空链表、单节点、双节点、带环等边界用例比直接提交 OJ 更高效。3.3 复杂度分析与代码健壮性链表题的解法通常不复杂但复杂度分析一定不能错。常见操作遍历一次O(n)反转链表 O(n)快慢指针找环 O(n)严格说是 O(n)快指针可能多走若干步但线性量级不变合并两个有序链表 O(mn)空间复杂度也要说清楚迭代反转是 O(1)递归反转是 O(n)栈开销。面试时这个点经常被追问你最好主动说出来显得你是真的懂而不是背模板。在代码健壮性上我建议所有链表函数开头都写if (head NULL) { return NULL; // 或 return head; }别嫌多这一行能挡住很多空指针事故。有些题返回类型是struct ListNode*空链表返回 NULL 就对了如果要对链表内容做修改比如删除节点空链表直接返回空头即可。4. 链表OJ从入门到进阶的刷题路线4.1 力扣必做链表题清单我按难度给你整理了一个清单你可以照着刷入门203 移除链表元素、206 反转链表、876 链表的中间结点、21 合并两个有序链表进阶141 环形链表、142 环形链表 II、160 相交链表、19 删除链表的倒数第 N 个结点再进阶138 复制带随机指针的链表、23 合并 K 个升序链表、25 K 个一组翻转链表你可能会问为什么有这么多题因为链表考点就这么几个遍历、反转、快慢指针、删除、合并、复制、特殊操作比如重排把这些题吃透基本就能应对考研、期末和面试了。不要追求刷多少道而是每一道都画图、写完整代码、跑测试样例、分析复杂度这样刷十道抵别人刷五十道。4.2 考研/期末中的链表题怎么准备如果你在准备考研数据结构408或期末考链表题通常以两种形式出现手写代码题和选择题/解答题。手写代码题要求你在纸上写完整函数。考研阅卷时比较看重逻辑清晰和关键点正确不会要求你编译通过当然也不能有明显语法错误。我建议你把反转链表、合并有序链表、链表插入删除这几个基本操作做成“肌肉记忆”闭着眼睛都能写出来。同时注意一些规范malloc函数对应的free修改链表后尾节点置NULL这两个点阅卷老师特别爱挑错。选择题/解答题则经常考带头结点和不带头结点的区别、循环链表的判空条件、双向链表删除操作的指针修改顺序等。这部分不用写大量代码但概念要理清。我备考时把王道书上的课后题拿来反复做重点题型做了三遍以上。4.3 链表在实际工程中的样子你以为链表只活在 OJ 和试卷里那就错了。我在嵌入式开发和操作系统的实际代码里经常遇到链表。拿嵌入式来说内核模块往往用链表管理设备列表最常见的是双向循环链表。Linux 内核里有一个经典的struct list_head它不包含数据字段而是把链表结构嵌到业务结构体中靠container_of宏获取业务数据的地址。这种设计让你在写驱动时可以用同一个链表函数操作成千上万种不同结构体。初看可能有点绕但它本质还是“指针串节点”的思想和你在 OJ 里刷的链表没有区别。链表在现实工程中还经常被用来做缓冲队列、内存池的空闲块管理、任务调度队列。说白了只要数据数量不确定、频繁插入删除链表类结构肯定比数组更灵活。所以你在刷题时多花点时间把每种操作的指针改法搞清楚以后看内核源码或者写项目都能省很多力。5. 我自己刷链表OJ的几条心得最后倾囊相授几条实在的经验。第一不要盲目相信一次 ACAccepted通过。就算一遍通过了也回去看看官方题解或讨论区看看有没有更精巧的写法。比如有人用递归写反转有人用迭代两种都写一遍理解完全不一样。第二一定要构造测试用例。很多人只会用题目给的样例这样很难发现边界问题。我每次都会拿空链表、一个节点、两个节点、节点值为相同的链表逐一测试测试用例全过再提交 OJ。这套方法帮我避掉了很多“为什么本地能过提交就挂”的鬼问题。第三链表题非常适合在纸上演算。你不需要多么高端的画图工具拿一支笔和一张草稿纸就够了。遇到不会的先不要马上看题解试着在纸上把指针操作一步步画出来很多时候画着画着思路就通了。第四善用虚拟头节点和“保存后继”这两个操作。虚拟头节点让头部的处理变得统一保存后继让你在任何时候都不会丢链。这两招几乎能破解八成以上的链表修改类题目。我先说这些你自己去动手写吧。链表这东西光看不练永远学不会动手写十道题之后你会觉得它比数组还简单。