1. 为什么单链表在OJ里这么能打1.1 单链表是所有链式结构的基本盘我做了这么多年算法题也带过不少新人刷题发现一个特别普遍的规律很多人在树、图这些复杂结构上栽跟头追根溯源往往不是思路问题而是单链表的基本功不够扎实。树本身就是一个节点有多个指针域的链表变体图的邻接表更是链表的直接应用所以单链表学成什么样直接决定你后面能走多远。单链表在OJ题里的地位很特殊。它不像数组那样可以直接按下标访问也不像哈希表那样可以O(1)查值它逼着你只能用指针去“走”这种思维方式恰恰是理解复杂数据结构的起点。比如你理解了两数相加这道题里“进位怎么传递到下一个节点”那你在处理二叉树层序遍历时的节点串联时就会自然很多。考研数据结构里单链表是必考内容。408那张卷子图和数组的题目年年变但链表的考察逻辑从来没变过——就是看你能不能处理好指针的指向关系。我在带考研学生复习时反复强调过单链表的OJ题不是让你背代码而是让你在无意识中建立一种“指针预判”能力看到next的赋值顺序脑子里面就能浮现出节点之间是怎么断链、怎么接上的。1.2 OJ题目里单链表的典型考法把常见平台上的单链表题目拉出来看考法其实非常集中。反转类整表反转、区间反转、合并类合并两个有序链表、K个有序链表合并、环相关是否有环、环入口、删除类删除倒数第N个节点、删除重复节点、以及寻找类找中间节点、找链表交点这五类基本覆盖了90%以上的单链表OJ题。这些题目在设计上有一个共同点不会让你去做复杂的数值计算或字符串处理而是反复考察你对“指针变更顺序”的掌控力。比如删除倒数第N个节点解法核心是用快慢指针但很多人写出来依然报错原因就是没有想清楚快指针先走N步之后慢指针到底指向的是待删节点还是待删节点的前驱。这个细节不弄明白换个题目包装你就又不会了。这也是我认为单链表OJ题特别值得做复盘的原因。它的核心就那么多但每道题都在不同的场景里变着花样考同一个本质。复盘的价值就是把这一堆看起来纷繁复杂的题目压缩成几个你真正掌握的思维模型。2. 动手之前单链表的基本功你必须焊死2.1 结构定义与指针语义任何单链表的OJ题首先得把结构体定义搞清楚。C语言里最常见的定义长这样struct ListNode { int val; struct ListNode *next; };就这么一个简单的结构体已经能看出门道。val存储数据next存的是下一个节点的地址注意是地址不是节点本身。很多刚刷题的人混淆了“指针”和“节点”的概念以为p-next就是下一个节点严格来说p-next是下一个节点的地址p-next才代表通过这个地址访问到的那个节点。这个语义搞不清楚操作起来就会出现一种很尴尬的情况你想删除当前节点p你写了free(p)然后就不知道怎么办了因为你在free之前已经把p-next的值存在一个临时变量里了这没错但很多人是free完了才想起要保存next结果就是野指针访问程序直接崩溃。我自己的习惯是动手写代码之前先在草稿纸上把节点画出来用方框表示节点用箭头表示指针。箭头从哪个框出发指向哪个框写代码的时候箭头的方向就是赋值的方向。这个习惯看起来很笨但真的能解决掉一大批“指针指飞”的问题。2.2 头结点与二级指针的坑单链表OJ题里关于头结点的坑至少值10分。很多平台的题目会告诉你链表可能有头结点dummy head也可能没有但函数签名往往是struct ListNode* reverseList(struct ListNode* head)这里传进来的是一个指向第一个数据节点的指针。问题是如果你在函数内部需要修改head本身比如删除头节点这时候单靠这个一级指针是不够的。要修改传入的指针本身必须得用二级指针或者用返回值的方式。实战中我最推荐的处理方式不是去纠结二级指针而是统一用哑结点。也就是在真正的头节点前面加一个虚拟节点让整个链表的操作逻辑变成“永远不操作真正的头节点”。加哑结点之后删除任何节点都变成了删除中间节点逻辑就统一了。这里要特别注意哑结点的val是没意义的通常初始化为0或-1不要让它参与业务逻辑计算。2.3 关于哑结点的使用心得哑结点的坑也有一个很多人加上之后最后返回的时候搞不清楚应该返回什么。struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode dummy; dummy.next head; struct ListNode* prev dummy; struct ListNode* curr head; while (curr) { if (curr-val val) { prev-next curr-next; curr prev-next; } else { prev curr; curr curr-next; } } return dummy.next; }这里第一个容易踩的坑是dummy用struct变量还是用指针。上面的代码里dummy就是个栈上的结构体变量取地址传给prev这没问题因为函数结束前dummy的生命周期都有效。但如果你写成struct ListNode* dummy malloc(...)你就得记得free掉不free就是内存泄漏。第二个坑是更新指针的时机。看上面的代码当val匹配时prev不动curr指向prev-next也就是被删除节点的下一个不匹配时prev和curr都往前走一步。这个节奏是配合prev-next的更新的一旦节奏错了链表就断了。我见过很多人在这里写成了curr curr-next乍一看没问题但如果curr是被free掉的节点那你就是在访问野指针了。3. 高频OJ题逐个拆解3.1 反转链表的迭代与递归两种写法反转链表应该是单链表OJ里最经典的一道题没有之一。面试考它、笔试考它、考研也考它。我见过不少学生把迭代版背得滚瓜烂熟但一问递归版怎么写人就愣住了。这里我强烈建议两种都要会因为递归写法是理解“链表天然具有递归结构”的最好入口。迭代版的核心是三个指针prev、curr、nextTemp。每一步先把curr的下一个节点存下来然后把curr的next指向prev最后三个指针整体后移。struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* curr head; while (curr) { struct ListNode* nextTemp curr-next; curr-next prev; prev curr; curr nextTemp; } return prev; }这段代码别看短里面至少藏着两个新手必踩的坑。第一很多人会忘记保存curr-next直接写curr-next prev结果链表后半段直接丢了。第二循环结束条件是curr ! NULL不是curr-next ! NULL如果写成后者链表压根反转不了。这些坑我在第4节会专门展开说。递归版的思路则是反转以head为头的链表等价于先反转head-next为头的子链表然后把head接到子链表反转后的末尾。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置为NULL是为了防止链表成环。我在讲这个写法的时候特别喜欢让学员画出递归的“展开—回归”过程画懂了之后很多链表递归题就会了。3.2 合并两个有序链表合并两个有序链表是另一个高频题目也是归并排序思想在链表上的应用。题目本身不难但能延伸出K个有序链表合并那就涉及优先队列了。合并的核心逻辑就是比较两个链表当前节点的值谁小接谁struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; struct ListNode* tail dummy; dummy.next NULL; while (list1 list2) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } tail-next list1 ? list1 : list2; return dummy.next; }很多人在循环结束后写的是一段“尾巴处理”代码把剩余的节点逐个接上。其实完全没必要剩余的那段链表本身就已经是有序的直接把tail-next指过去就行了。这个优化点虽然不起眼但是体现了你对链表结构的理解——你操作的是节点之间的指针不是逐个拷贝节点值。另外注意list1和list2都没改动原来的其他节点关系所以如果题目要求“不能破坏原链表结构”这个解法本身就是满足的。但有些题目要求合并之后新链表不能复用旧节点必须新建节点那就是另一道题了需要区分清楚。3.3 链表中环的检测环形链表这道题快慢指针是经典解法。快指针每次走两步慢指针每次走一步如果有环它们一定会在环里相遇。这个结论很多人背下来了但不理解为什么快指针步长为2而不是3或4。简单说步长为2时快慢指针的相对速度是1也就是每走一步两者距离缩小1。假设它们之间相差k个节点k步之后必然相遇。但如果快指针步长为3相对速度是2如果距离差是奇数会出现快指针“越过”慢指针的情况虽然最终仍可能相遇但需要额外的条件分析起来更复杂。所以做题的时候老老实实步长为2就完了。bool hasCycle(struct ListNode *head) { if (head NULL || head-next NULL) return false; struct ListNode* slow head; struct ListNode* fast head-next; while (slow ! fast) { if (fast NULL || fast-next NULL) return false; slow slow-next; fast fast-next-next; } return true; }需要注意这段代码里slow从head开始fast从head-next开始这是为了避免一开始slow fast导致误判。很多人写成slow head, fast head然后在循环里先移动再比较也能行得通但逻辑上要小心第一次进循环时两者相等会直接返回true。我推荐的写法就是先让fast走一步这样判断起来更直观。3.4 删除倒数第N个节点删除倒数第N个节点我愿称之为快慢指针的最经典实战。思路很简单快指针先走N步然后快慢指针一起走快指针走到尾慢指针指向的就是倒数第N个节点的前驱。然后执行删除。但这里有个很容易被忽略的边界情况如果倒数第N个节点是头节点呢如果快指针走了N步正好走到了NULL说明链表长度就是N要删除的就是第一个节点。这时候需要特殊处理。用哑结点可以完美化解这个尴尬struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode dummy; dummy.next head; struct ListNode* fast dummy; struct ListNode* slow dummy; while (n--) { fast fast-next; } while (fast-next) { fast fast-next; slow slow-next; } struct ListNode* delNode slow-next; slow-next delNode-next; free(delNode); return dummy.next; }这段代码里我故意用了free操作因为这是OJ题里容易被忽略的“卫生问题”。很多刷题平台是运行一次就退出不free也检查不出来但如果你去企业面试面试官很可能会问你“被删除的节点要不要释放内存”。释放是一种好习惯但要确保是真正不再使用的节点才释放。另外fast和slow都从dummy出发步数差刚好是N所以slow就是待删节点的前驱。头节点需要删除时因为fast走了N步后指向NULL此时fast-next访问就会崩溃但我们第二段循环条件写的是fast-next所以压根不会进入循环直接就走到了删除分支边界就被哑结点消化了。3.5 寻找链表的中间节点找中间节点是快慢指针最简单的应用快指针每次走两步慢指针每次走一步。快指针到链尾时慢指针恰好在中点。这道题有意思的地方在于“中间节点”的定义。链表长度为奇数时中间节点只有一个为偶数时有的题目说中间节点是第n/2个偏左有的说是第n/21个偏右。不同的定义怎么写如果是偏左struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast-next fast-next-next) { slow slow-next; fast fast-next-next; } return slow; }如果是偏右LeetCode上那道题的常用解法struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }这两个版本我能连在一起讲的原因就是想让读者看到“快指针的跳跃节奏不同慢指针停的位置也不同”。你在考场上不需要背代码你只需要画一次图记住“快指针走到边界时慢指针在哪里”就好了。边界判断条件是fast还是fast-next本质上决定了你是允许快指针再跳最后一跳还是必须停下来。4. 实操现场一次完整的OJ复盘记录4.1 从读题到暴力解再到优化很多刷题文章只讲最优解我觉得这是不全面的。真正做OJ复盘必须把“怎么想到这个解法”的过程还原出来否则读者就算看懂了答案下次遇到同类题还是不会。拿反转链表来说正常人在没学过这个解法之前第一反应是能不能把链表遍历一遍把所有节点的值存在数组里然后倒序再赋回去这就是暴力解。struct ListNode* reverseList(struct ListNode* head) { int arr[10000]; int count 0; struct ListNode* p head; while (p) { arr[count] p-val; p p-next; } p head; for (int i count - 1; i 0; i--) { p-val arr[i]; p p-next; } return head; }这个解法完全正确时间复杂度O(n)空间复杂度O(n)。OJ能过面试能讲但不是一个让人眼前一亮的解法。复盘时你要问自己能不能把空间省掉数组存在的意义是记录遍历顺序那我们能不能直接在原链表上“就地”反转指针于是引出了迭代三指针法。我复盘每一道链表题时都会先写暴力解再思考优化。这个过程还原的不是“最优答案”而是思考路径。阅读一篇好的复盘文章跟着作者走一遍从坏到好的过程比直接背诵最优解有价值得多。4.2 边界测试与提交踩坑线上OJ提交最大的特点就是你面对的测试用例是黑盒的可能只有几个公开样例剩下全是隐藏边界。我做了一堆单链表题后总结出一个必测边界清单空链表head NULL只有一个节点只有两个节点删除头节点删除尾节点链表有奇数个节点 / 偶数个节点输入的两个链表一个为空另一个正常拿删除倒数第N个节点来举例你以为你写的代码逻辑没问题结果提交上去报错。最可能的原因就是对某个边界没有处理。我用上面的哑结点写法空链表时dummy.next NULL返回也是NULL完全没问题。一个节点时fast先走1步到了NULL第二段循环进不去slow还是dummy删除slow-next即头节点返回dummy-next即NULL正确。这些边界不是靠灵光一现而是靠复盘时形成条件反射拿到题目先列边界写完后逐一验证。4.3 复杂度分析是复盘的灵魂说实话很多同学刷题题目AC了就算完从来不写复杂度分析。我强烈不建议这样。单链表OJ的复杂度分析特别能体现你对代码的理解程度。以环形链表为例快慢指针解法的时间复杂度是O(n)这不难。但空间复杂度为什么是O(1)因为只用到了两个指针变量不随链表长度增加而增长。对比用哈希表记录的解法空间复杂度O(n)高下立判。这一道题就点明了“双指针为什么总被面试官偏爱”——它能用O(1)空间解决O(n)空间才能解决的问题。再比如合并有序链表常规解法时间复杂度O(mn)这是因为每个节点都要比较一次。空间复杂度O(1)因为没有额外开数组。但如果你用递归写合并系统栈的深度是mn虽然OJ不报错但你要知道这个递归版本的空间复杂度其实是O(mn)。面试官如果追问一句“递归版和迭代版除了代码简洁度之外还有啥区别”你要能答上来。复盘时把时间复杂度和空间复杂度都写一遍不是为了交作业而是为了强迫你理解你的代码在资源层面做了什么事。这对后续学复杂数据结构是个非常重要的基本功。5. 刷题复盘方法怎么让每道题都不白做5.1 复盘四步法我在学习和带新人的过程中逐渐形成了一套自己的复盘方法一共四步。第一步重新独立写一遍代码不要看答案。做完之后哪怕AC了也要把代码关掉重新凭记忆和思路再写一遍。第二个版本不用完全一样思路对就行这一步的目的是验证你到底掌握了多少。第二步至少写出一种不同思路的解法。比如反转链表你学会了迭代法那递归法必须也得写出来。如果你只能写出一种解法说明你对这个知识点的理解是线性的不是网状的。另一种解法往往是从另一个角度切入同一个问题能帮你发现自己思维的盲区。第三步把代码的边界情况列成一个表。我常用的表格是这样的测试场景输入预期输出实际表现空链表NULLNULL需验证单节点[1]反转后[1]需验证双节点[1,2]反转后[2,1]需验证普通多节点[1,2,3,4]反转后[4,3,2,1]需验证每次提交之前先把这个表过一遍。可能不全但是能覆盖绝大多数边界。第四步隔一段时间再刷一次。我自己的节奏是当天、三天后、一周后、一个月后各刷一遍。每次刷都要求自己30分钟以内搞定超时就要重新复盘。5.2 错题本整理技巧错题本不是把题目抄一遍而是记录“错因”。我自己会把错因归成几类指针语义理解错误比如把next当成节点本身边界条件遗漏空链表、单节点、头尾操作循环条件错误while循环写成死循环或提前退出内存问题忘了free、访问了已释放的内存思路不清晰AC了但不明白为什么碰巧蒙对其实还有第六类就是“代码正确但效率不行”这个在单链表题目里相对少见但如果遇到了大概率是你在循环里做了重复遍历。整理错题本时要写清楚题目是什么、我看到这题的第一思路是什么、卡在哪一步、正确解法是什么、错因属于哪一类。分类很重要因为下次你再遇到类似错误你会一眼识别出“这是我之前犯过的指针语义错误”从而快速纠正。5.3 常见错误速查表我把单链表OJ里出现频率最高的错误整理成了一张速查表每次写链表代码前都对照一遍错误类型具体表现正确做法遍历时提前断链修改cur-next前没保存后继先存tmp cur-next再改指向循环条件写错用cur-next ! NULL做循环条件导致尾节点没处理确认循环边界到底处理到哪个节点返回节点错误返回了哑结点而不是哑结点-next明确返回值的语义删除节点后指针悬空free之后继续访问该节点free之前先保存必要信息操作头节点时丢失头指针修改了head却没留下新的头指针用哑结点或先保存新头忘记处理空链表直接解引用head入口处增加判空递归没有终止条件递归版反转链表无限递归检查base case是否覆盖head NULL和head-next NULL这张表你在刷题前期可以放在手边刷到后期就要内化成肌肉记忆。我看到很多人做完题不看表结果同样的错误换了张卷子继续犯这就是复盘没做到位。6. 关于单链表OJ我还有一些想叮嘱的如果非要说单链表题和其他OJ题有什么不同我觉得是它对“细节”的要求到了一个令人生畏的程度。数组题你写了个1写成了-1可能只影响一个测试用例链表题你少了一个保存next的临时变量整个链表就丢了可能只对了一个样例剩下全错。所以我在实际带人刷题时始终坚持一个原则单链表这类型的题目必须用笔纸画图画完再写代码。一开始会觉得麻烦、浪费时间刷了二三十道题之后你会发现看题目时脑子里的链表结构已经能自动“动起来”了这时候画图就成了一种辅助而不是必要。还有一个每个人都会遇到的情况第一遍AC了第二遍还是会卡。这太正常了不要觉得沮丧。链表题目对短期记忆的依赖很小但对“动手模式”的依赖很大。你今天看着答案写出来了不代表你明天能独立写出来。所以间隔重复特别重要。另外提一句关于C和Python的选择。很多人考研或者刷力扣习惯用PythonPython里链表节点的定义是class ListNode: def __init__(self, val0, nextNone): self.val val self.next next因为Python的引用来等于指针所以核心逻辑和C是一样的。但Python里没有free不需要管内存释放同时你也要注意Python的“引用”在局部变量上的行为有时会让初学者困惑——你在函数里new了一个新节点函数返回之后节点还活着这和在C里栈上分配可不一样。我之前带过的一个学员一直用C刷链表题后来转Python的时候特别不适应“没有指针”这个概念其实Python里每个变量都是指针只是不需要你显式声明。理解了这一点之后他回C反而更通透了。单链表的OJ复盘到这儿我该说的都说差不多了。最后再分享一个小技巧如果你刷题一段时间后遇到瓶颈不妨回头把已经AC过的链表题重新做一遍限时、不看旧代码。你会发现那些你以为掌握得很好的题目其实还有一些细节已经悄悄忘了。这个过程很痛苦但真的有效。