链表这个章节很多初学者在概念上都能背出来节点存数据指针连起来最后一个节点指向空。但一到OJ平台做题画风就完全变了——要么空指针异常要么反转链表转出一个死循环要么删了半天发现头节点的值根本没删掉。我当年学数据结构的时候链表题几乎是我第一次感受到“课上听懂了作业不会做”的挫败感。这篇笔记是《数据结构初阶笔记归纳》系列的第七篇专门把链表OJ题按类型、按套路拆开讲。我会把删除、反转、快慢指针、合并相交、环形链表这些高频题型串起来每一类都给出核心思路、可直接复制的代码和边界条件的处理方式。适合正在学数据结构的学生、准备机考或面试的初学者也适合那些链表题反复报错、想系统总结一遍的人。因为链表题的解法套路其实非常固定一旦掌握了“画图 边界 哨兵位”这套组合拳后面刷题会顺畅很多。这篇就把我自己实践下来最有效的方法和踩过的坑一次性交代清楚。1. 动手前先把这三件事想清楚1.1 为什么链表题一写就崩链表题容易出错根源在于它和数组的思考方式完全不同。数组是连续的arr[i]想访问哪个就访问哪个越界了编译器还会给你报错链表只能顺着指针一个一个走你手里永远只有当前节点的视图看不到“前面”也看不到“后面”。人脑不擅长这种“只能往前走”的逻辑特别是涉及多个指针交替移动的时候稍微一走神就把节点弄丢了。我在带一位学弟调代码时发现他写删除链表节点的逻辑时总喜欢在循环里同时改三四个指针结果他自己也说不清每个指针指向哪里。这不是智商问题是思考方式的问题。链表题的正确打开方式只有一个——画图。画一个包含三个节点的链表把prev、cur、next这三个指针的位置标出来走一步画一步你会发现原本一团乱麻的逻辑会变得非常清晰。我自己写链表OJ题的标准流程是先在草稿纸上画链表然后写出指针变化步骤最后才打开编辑器写代码。一步到位直接写代码的人绝大多数都会在边界条件上翻车。1.2 边界条件的“三个魔鬼”链表题里有个现象核心逻辑写对了但提交时总有几个用例挂掉。这几乎都是边界条件没处理干净。第一个魔鬼是空链表。很多新手在函数开头不加判断上来就head-val空链表直接空指针异常。这不是算法问题是防御性编程习惯问题。第二个魔鬼是单节点链表。比如反转链表时只有一个节点循环能不能正常退出快慢指针找中点时一个节点能不能正确返回这些都需要单独验证。第三个魔鬼是头节点和尾节点。删除节点时如果要删的是头节点你的代码能不能正确处理如果要删尾节点循环会不会走到空指针上我的习惯是每道链表题写完先在脑子里跑三个测试用例——空链表、单节点链表、普通多节点链表。跑完这三个再提交OJ通过率能明显提升。1.3 哨兵位虚拟头结点到底该不该用链表题里有一个非常重要的工具——哨兵位也叫虚拟头结点。它的作用非常朴素让头节点的处理逻辑和普通节点保持一致避免“删除头节点”这种特殊情况单独写一个if。举个例子题目要求删除链表中所有值等于val的节点。不用哨兵位的写法是先判断头节点是否需要删除如果是就移动头节点然后再处理中间节点。你会发现头节点被特殊对待了代码里必须写一个while循环单独处理头。用哨兵位之后情况完全不一样struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); dummy-next head; struct ListNode* cur dummy; while (cur-next ! NULL) { if (cur-next-val val) { struct ListNode* tmp cur-next; cur-next tmp-next; free(tmp); } else { cur cur-next; } } struct ListNode* ret dummy-next; free(dummy); return ret; }哨兵位的核心价值在于它是一个不参与业务逻辑的额外节点让cur永远有一个“前驱”这样删除操作就统一变成“删除cur的下一个节点”头节点的特殊性被抹平了。这个技巧在合并链表、分隔链表、删除倒数第N个节点等题目里都会用到。但哨兵位也不是万能的。如果题目本身要求返回头节点比如反转链表或者不需要处理“删除头节点”这种特殊情况那强行加哨兵反而会让代码变复杂。判断标准很简单如果头节点可能被改变就用哨兵如果头节点在整个过程中不会变就用普通双指针。2. 链表OJ的五大类型题链表题虽然五花八门但按知识点了归类其实就五大类型。先看一张总览表题型代表题目核心考点难度删除与构造移除链表元素、删除倒数第N个节点前驱指针、哨兵位初阶反转类反转链表、回文链表三指针迭代、递归初阶到中阶快慢指针中间节点、环形链表快慢指针数学原理中阶合并与相交合并有序链表、相交链表哨兵位、步数对齐初阶到中阶复杂结构复制随机指针链表、链表排序哈希映射、归并思想中高阶下面我按这个分类把每类题目最核心的解题套路拆开讲。2.1 删除与构造类核心是“前驱指针”删除类题目的共通思路是想删掉某个节点必须知道它的前驱节点。链表的单向性决定了你无法回头找前驱所以遍历过程中要时刻用一个prev或cur指针站在“前驱”的位置上。上面已经给了移除链表元素的完整代码这里重点说一个容易踩的坑删除节点时free之后千万不要继续访问tmp-next。很多新手刚free(tmp)下一行又去读tmp的数据这在本地可能不报错但OJ上跑起来就是未定义行为有时候是随机崩溃有时候是运行结果不对。删除倒数第N个节点这道题也很有代表性。它要求先找到倒数第N个节点但单项链表不能从后往前遍历所以常规做法是快指针先走N步然后快慢指针同步前进快指针走到空时慢指针正好在待删除节点的前驱位置。这里还要注意一个细节如果N等于链表长度删除的是头节点用哨兵位处理会简单很多。构造类题目里分隔链表值得一提。它要把所有小于指定值x的节点放在大于等于x的节点之前。常规解法是维护两个子链表一个装小的一个装大的最后把两个链表接起来。这道题用哨兵位特别舒服因为两个子链表的头都是动态拼接的用哨兵位避免了一堆if判断。2.2 反转类迭代三指针与递归反转链表是整个链表题里的“题眼”很多进阶题目都建立在反转的基础上。迭代写法是标准的“三指针”操作prev指向已反转部分的头cur指向当前要处理的节点next保存下一个节点。struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; // 先保存下一个不然断了就找不回来 cur-next prev; // 当前节点掉头指向前一个 prev cur; // prev前进 cur next; // cur前进 } return prev; // 最终prev就是新的头 }这里最关键的是一行struct ListNode* next cur-next;。如果不先保存执行cur-next prev之后原来的cur-next就丢了链表从中间断成两截。这个错误我见过太多次了错误代码写出来是好看的跑起来就完蛋。递归写法理解起来更难但代码极短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这一行——它在把后一个节点的指针掉头指向当前节点。初学递归时不用强行理解所有细节先照着写画图走几遍慢慢体会。2.3 快慢指针类中间的数学原理快慢指针的典型应用有三个找中间节点、找倒数第K个、检测环形链表。找中间节点的代码非常短struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这个代码为什么能得到中间节点因为慢指针走一步时快指针走两步快指针到达末尾时慢指针恰好走了一半路程。有一点要注意偶数节点个数时这个写法返回的是靠右的中间节点。比如4个节点slow会停在第三个节点。不同题目对返回位置的要求不一样需要根据题意调整。环形链表的检测思路是快指针每次走两步慢指针每次走一步如果链表有环快指针迟早会追上慢指针两者相遇。bool hasCycle(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }为什么一定能相遇想象两个人在环形跑道上跑步一个速度快一个速度慢速度差固定快的迟早会从后面追上慢的。至于为什么快指针要一次走两步而不是三步、四步因为两步可以保证每一步两个指针的距离变化为1不会出现跨过对方没碰到的情形。这个数学原理在进阶题“找到环的入口”里会更清晰。设链表起点到环入口的距离为a环的长度为b。快慢指针相遇时慢指针走了s步快指针走了2s步两者路程差为s这个s必然是环长b的整数倍因为快指针比慢指针多走了若干圈。所以slow s kb。此时你让一个指针从链表头重新出发另一个指针从相遇点出发两个都每次走一步。从头出发的指针走a步到达环入口时从相遇点出发的指针也走了a步。因为相遇点在环上的位置是s mod b 0即相遇点就是环入口的等价位置所以它走了a步后也到达环入口两指针必然在入口相遇。这个结论就是环形链表II这道题的解法基础。2.4 合并与相交类哨兵位与步数对齐合并两个有序链表我会用哨兵位 尾插法来实现。思路很直接同时遍历两个链表谁小就接谁最后把剩下的部分整体拼上去。struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); 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; struct ListNode* ret dummy-next; free(dummy); return ret; }这个题在初阶阶段必须达到闭眼能写的程度因为它是很多分治算法的基础比如链表的归并排序就要用它做合并步骤。相交链表这道题非常巧妙它要求找两个链表第一次相交的节点。最直观的解法是哈希表遍历A链表把所有节点地址存起来再遍历B链表第一个在哈希表中出现的节点就是交点。但更符合链表思维的解法是两个指针的“步数对齐”struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { if (headA NULL || headB NULL) { return NULL; } struct ListNode* pA headA; struct ListNode* pB headB; while (pA ! pB) { pA (pA NULL) ? headB : pA-next; pB (pB NULL) ? headA : pB-next; } return pA; }它的原理是如果A链表的长度为a mB链表的长度为b m其中m是公共部分的长度。pA走完A再走B总路径长是a m bpB走完B再走A总路径长是b m a两者相等。这意味着两个指针在第二次遍历时一定会同时到达交点。如果两个链表不相交它们会同时走到NULL循环自然退出。2.5 进阶类值得知道的几道题初阶阶段的链表题里有几道题可以作为进阶挑战学有余力时看看会有很大收获。“复制带随机指针的链表”是经典的中等偏上题目。它的难点在于每个节点除了next指针外还有一个random指针直接深拷贝时random指向的节点可能还没创建。常规解法是用哈希表建立原节点和新节点的映射关系第一遍遍历创建新节点并记录映射第二遍遍历根据映射设置random。还有更进阶的O(1)空间做法在原链表的每个节点后插入一个拷贝节点然后利用原节点的random来设置拷贝节点的random最后分离链表。这个做法不要求初阶掌握但能锻炼对链表结构的理解。链表排序也是进阶重点。数组排序可以直接用下标访问链表排序最稳定的思路是归并排序——先找到中点拆成两半递归排序再合并。你会发现快慢指针和合并有序链表这两个技能在这里全部用上了。3. 从一道题到一类题三种可以迁移的思路3.1 反转链表是一块万能积木反转链表为什么是核心因为它的变换能力太强了。判断回文链表常规做法是先用快慢指针找到中点然后把后半部分反转再从前半部分头节点开始同步比较。这个题把“快慢指针找中点”和“反转链表”两个技巧组合在一起解出来了会很有成就感。再看“反转链表II”它要求反转从第m个节点到第n个节点之间的部分。这个题不是无脑全反转而是要先定位到m位置的前驱然后对局部做反转。我实际做的时候发现把第m个节点的前驱记为pre然后从第m个节点开始执行m到n之间的反转逻辑边界条件非常容易错。一个小技巧是把pre-next一直指向新反转后的头节点同时用一个cur指针指向原始的第m个节点因为反转完之后这个cur应该成为局部链表的尾节点它的next要接上第n1个节点。3.2 快慢指针的适用范围比想象中大快慢指针不只能找中点和检测环它还能用来找链表倒数第K个节点。思路是快指针先走K步然后快慢指针同步走快指针到末尾时慢指针指向的就是倒数第K个。这个思路本质上也可以理解成“用快指针制造一个长度为K的窗口”让窗口整体滑动到链表末尾。快慢指针的升级应用是“重排链表”。题目要求把L0 - L1 - ... - Ln-1 - Ln重排成L0 - Ln - L1 - Ln-1 - L2 - Ln-2 ...。做法是先找到中点把后半部分反转然后交替合并两个链表。这里每一步都是前面讲过的内容但组合起来题目难度立刻上了一个台阶。我的体会是初阶阶段不一定要把这种题做出来但至少要有“拆解成多个已知步骤”的意识这样刷题才会有积累感。3.3 哨兵位在什么地方都管用哨兵位除了用在删除和合并外在“分隔链表”“链表排序中合并两个已排序链表”等场景里也很管用。比如给出一个链表和一个值x要求将所有小于x的节点放在所有大于等于x的节点之前。这时候你可以开两个哨兵位节点一个挂接小于x的节点一个挂接大于等于x的节点遍历结束后把两个链表拼接即可。整个过程把头节点的动态变化全部隐藏了代码干净的让你怀疑是不是在写链表题。我的建议是从初学阶段开始每周挑一道用哨兵位的题目练手直到形成条件反射——“这道题的头节点可能变吗可能变就加哨兵。”一旦形成这种条件反射你在OJ上的通过率会有一个明显的跃升。4. OJ提交时的常见报错与排查套路4.1 空指针解引用链表题最常见的报错就是“访问了空节点的成员”编辑器或OJ给的提示通常是Segmentation fault或者空指针异常。我见过的最典型错误是删除节点时没判断当前节点是否为空直接cur-next-val当cur-next是NULL时就炸了。还有一个隐蔽的场景使用快慢指针时fast-next-next。如果fast-next本身是NULL访问fast-next-next就会出问题。所以代码里while (fast ! NULL fast-next ! NULL)这个判断顺序是有讲究的先判断fast不为空才能访问fast-next判短路的保证了第二个条件只在第一个条件成立时才会执行。4.2 死循环链表题死循环的常见原因是反转链表时没有把最后一个节点的next改成NULL。举个具体场景反转时cur-next prev遍历结束后prev指向原链表的最后一个节点cur指向NULL。如果中间某个节点没有正确断开原来的连接链表就会形成一个环OJ提交直接超时。另一个死循环场景发生在快慢指针里。如果你把快指针更新写成fast fast-next; fast fast-next;而不是合并成fast fast-next-next需要考虑两步之间的空指针判断。一旦跳出循环的条件写错比如只判断了fast ! NULL而没判断fast-next ! NULL就可能死循环。排查死循环的一个好办法是加打印语句。在循环里打印当前节点的值如果发现某个节点反复出现基本就是环形成了。4.3 返回的头节点不对删除类题目如果不用哨兵位很容易在头节点被删除后返回一个失效的指针。举例删除头节点时如果你只是把head往后挪了却没有更新返回值或者更新了但后续函数里又使用了旧的head指针就会出错。我在实际调代码时发现一个很反直觉的现象有时候本地运行结果是正确的但OJ上就是不过。排查了半天发现是函数返回的头节点没有更新到全局变量里。链表题里如果你在子函数里修改了头节点要么通过返回值传出去要么传入二级指针否则外层函数拿到的永远是旧指针。OJ题目一般只要求返回新头节点所以用返回值就行。4.4 内存泄漏和悬垂指针OJ平台一般不会因为内存泄漏扣分因为进程跑完就回收了。但如果你在面试或本地调试时被问到最好具备这个意识。内存泄漏的典型场景删除节点时只改了前驱的next却没有free掉被删除的节点。这在OJ上可能不会报错但内存消耗会变大。悬垂指针的典型场景是先free了一个节点但还有一个指针指在它上面之后又通过这个指针访问数据。这就是未定义行为运气好没事运气不好直接崩溃。我的习惯是free掉一个节点后立刻把相关的临时指针置为NULL防止误用。4.5 调试三板斧链表题的调试我总结了三个非常实用的方法。第一小规模用例。不要一上来就构造十几二十个节点的链表去调试只用两三个节点的链表在纸上把每一步的指针变化写出来。第二打印中间状态。在关键节点打印当前节点值和当前指针地址观察是否符合预期。比如反转链表时在循环里打印prev-val、cur-val、next-val很快就能定位是哪里断开的。第三画图。这看起来是老生常谈但链表题里它真的比任何调试工具都管用。每一步画一下图指针关系一目了然比盯着代码猜要高效一百倍。5. 刷题顺序与现场考试的注意事项5.1 给初学者的刷题节奏链表OJ题忌讳一上来就挑战最难的也忌讳只做最简单的。我给学弟学妹们推荐一条相对平滑的路线你可以参考第一步先做删除类。移除链表元素、删除排序链表中的重复元素、删除链表的倒数第N个节点。这个阶段目标只有一个理解前驱指针学会用哨兵位。第二步做反转类。反转链表迭代和递归都要会、反转局部链表。这个阶段目标是把三指针反转练成肌肉记忆。第三步做快慢指针。链表的中间节点、环形链表、环形链表II。这个阶段需要理解数学原理如果只记住代码不理解推导下次换一个问法还是会卡住。第四步做合并与相交。合并两个有序链表、相交链表、两两交换链表中的节点。这个阶段会发现前面练的哨兵位、双指针技巧开始产生复利效应。第五步挑战综合题。回文链表、重排链表、链表排序。这些题目本身有一定难度但拆开来看每一块都是前面练习过的内容。5.2 时间分配的一个实际建议如果是准备期末考试或初阶机考不需要追求刷太多题。把上面列出的核心题每种类型挑两道总计十道左右反复做到不看答案能写出来效果远好于看完五十道题的解体思路却不自己动手。我自己带过的学生里进步最快的做法是每天只刷一道链表题但要把这道题做完所有变体。比如今天做反转链表就把迭代、递归、反转局部三个变体全写一遍。这样一周下来链表题的基本功就非常扎实了。考试前一周再用OJ平台自带的模拟测功能把常见题型过一遍重点测试边界条件处理。我发现很多人不是不会写而是考试时一紧张就忘了链表可能为空、头节点可能变这种基本前提最后挂在最简单的用例上。5.3 面试场景下的链表题要求如果是准备面试链表题的要求会比机考高一个档次。面试官看的不只是答案正确更看重你分析问题的思路和边界意识。我建议在面试前专门练习“白板写链表题”不用编辑器只用纸和笔。这听起来很像老古董但实际训练效果很好因为你不能在编译器的提示下发现问题必须在写之前就把所有边界条件想清楚。面试时如果做到“先画图、再讲思路、最后写代码”这个流程即使最后代码有小瑕疵面试官通常也会认可。另一个面试里常问的问题是时间复杂度和空间复杂度。链表题里的快慢指针、反转、合并都要能说清为什么是O(n)时间、O(1)空间哪些做法虽然简洁但额外用了O(n)空间。比如相交链表用哈希表是O(n)空间双指针法就是O(1)空间环形链表II用哈希表是O(n)空间快慢指针是O(1)空间。这些对比最好自己做一个笔记临场才不会卡壳。我个人在实际操作中最大的体会是链表OJ题最大的障碍从来不是语法而是缺少“边界感”。只要每次写代码前逼自己画一张图、想清楚空链表和单节点的场景就已经比绝大多数人做得好。最后再分享一个小技巧——刷链表题时准备一个固定的草稿本把每道题的指针变换图画在旁边隔天复习时看一眼图就能快速回忆起解法。这个习惯我保持了整个初阶学习阶段后续学二叉树、图结构时这种“先画图再写代码”的习惯也一直在帮我的忙。 
长河君 · 2026/10/18 10:36:28 · 阅读 1.2k 链表OJ题核心套路：哨兵位、快慢指针与边界处理详解
链表这个章节很多初学者在概念上都能背出来节点存数据指针连起来最后一个节点指向空。但一到OJ平台做题画风就完全变了——要么空指针异常要么反转链表转出一个死循环要么删了半天发现头节点的值根本没删掉。我当年学数据结构的时候链表题几乎是我第一次感受到“课上听懂了作业不会做”的挫败感。这篇笔记是《数据结构初阶笔记归纳》系列的第七篇专门把链表OJ题按类型、按套路拆开讲。我会把删除、反转、快慢指针、合并相交、环形链表这些高频题型串起来每一类都给出核心思路、可直接复制的代码和边界条件的处理方式。适合正在学数据结构的学生、准备机考或面试的初学者也适合那些链表题反复报错、想系统总结一遍的人。因为链表题的解法套路其实非常固定一旦掌握了“画图 边界 哨兵位”这套组合拳后面刷题会顺畅很多。这篇就把我自己实践下来最有效的方法和踩过的坑一次性交代清楚。1. 动手前先把这三件事想清楚1.1 为什么链表题一写就崩链表题容易出错根源在于它和数组的思考方式完全不同。数组是连续的arr[i]想访问哪个就访问哪个越界了编译器还会给你报错链表只能顺着指针一个一个走你手里永远只有当前节点的视图看不到“前面”也看不到“后面”。人脑不擅长这种“只能往前走”的逻辑特别是涉及多个指针交替移动的时候稍微一走神就把节点弄丢了。我在带一位学弟调代码时发现他写删除链表节点的逻辑时总喜欢在循环里同时改三四个指针结果他自己也说不清每个指针指向哪里。这不是智商问题是思考方式的问题。链表题的正确打开方式只有一个——画图。画一个包含三个节点的链表把prev、cur、next这三个指针的位置标出来走一步画一步你会发现原本一团乱麻的逻辑会变得非常清晰。我自己写链表OJ题的标准流程是先在草稿纸上画链表然后写出指针变化步骤最后才打开编辑器写代码。一步到位直接写代码的人绝大多数都会在边界条件上翻车。1.2 边界条件的“三个魔鬼”链表题里有个现象核心逻辑写对了但提交时总有几个用例挂掉。这几乎都是边界条件没处理干净。第一个魔鬼是空链表。很多新手在函数开头不加判断上来就head-val空链表直接空指针异常。这不是算法问题是防御性编程习惯问题。第二个魔鬼是单节点链表。比如反转链表时只有一个节点循环能不能正常退出快慢指针找中点时一个节点能不能正确返回这些都需要单独验证。第三个魔鬼是头节点和尾节点。删除节点时如果要删的是头节点你的代码能不能正确处理如果要删尾节点循环会不会走到空指针上我的习惯是每道链表题写完先在脑子里跑三个测试用例——空链表、单节点链表、普通多节点链表。跑完这三个再提交OJ通过率能明显提升。1.3 哨兵位虚拟头结点到底该不该用链表题里有一个非常重要的工具——哨兵位也叫虚拟头结点。它的作用非常朴素让头节点的处理逻辑和普通节点保持一致避免“删除头节点”这种特殊情况单独写一个if。举个例子题目要求删除链表中所有值等于val的节点。不用哨兵位的写法是先判断头节点是否需要删除如果是就移动头节点然后再处理中间节点。你会发现头节点被特殊对待了代码里必须写一个while循环单独处理头。用哨兵位之后情况完全不一样struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); dummy-next head; struct ListNode* cur dummy; while (cur-next ! NULL) { if (cur-next-val val) { struct ListNode* tmp cur-next; cur-next tmp-next; free(tmp); } else { cur cur-next; } } struct ListNode* ret dummy-next; free(dummy); return ret; }哨兵位的核心价值在于它是一个不参与业务逻辑的额外节点让cur永远有一个“前驱”这样删除操作就统一变成“删除cur的下一个节点”头节点的特殊性被抹平了。这个技巧在合并链表、分隔链表、删除倒数第N个节点等题目里都会用到。但哨兵位也不是万能的。如果题目本身要求返回头节点比如反转链表或者不需要处理“删除头节点”这种特殊情况那强行加哨兵反而会让代码变复杂。判断标准很简单如果头节点可能被改变就用哨兵如果头节点在整个过程中不会变就用普通双指针。2. 链表OJ的五大类型题链表题虽然五花八门但按知识点了归类其实就五大类型。先看一张总览表题型代表题目核心考点难度删除与构造移除链表元素、删除倒数第N个节点前驱指针、哨兵位初阶反转类反转链表、回文链表三指针迭代、递归初阶到中阶快慢指针中间节点、环形链表快慢指针数学原理中阶合并与相交合并有序链表、相交链表哨兵位、步数对齐初阶到中阶复杂结构复制随机指针链表、链表排序哈希映射、归并思想中高阶下面我按这个分类把每类题目最核心的解题套路拆开讲。2.1 删除与构造类核心是“前驱指针”删除类题目的共通思路是想删掉某个节点必须知道它的前驱节点。链表的单向性决定了你无法回头找前驱所以遍历过程中要时刻用一个prev或cur指针站在“前驱”的位置上。上面已经给了移除链表元素的完整代码这里重点说一个容易踩的坑删除节点时free之后千万不要继续访问tmp-next。很多新手刚free(tmp)下一行又去读tmp的数据这在本地可能不报错但OJ上跑起来就是未定义行为有时候是随机崩溃有时候是运行结果不对。删除倒数第N个节点这道题也很有代表性。它要求先找到倒数第N个节点但单项链表不能从后往前遍历所以常规做法是快指针先走N步然后快慢指针同步前进快指针走到空时慢指针正好在待删除节点的前驱位置。这里还要注意一个细节如果N等于链表长度删除的是头节点用哨兵位处理会简单很多。构造类题目里分隔链表值得一提。它要把所有小于指定值x的节点放在大于等于x的节点之前。常规解法是维护两个子链表一个装小的一个装大的最后把两个链表接起来。这道题用哨兵位特别舒服因为两个子链表的头都是动态拼接的用哨兵位避免了一堆if判断。2.2 反转类迭代三指针与递归反转链表是整个链表题里的“题眼”很多进阶题目都建立在反转的基础上。迭代写法是标准的“三指针”操作prev指向已反转部分的头cur指向当前要处理的节点next保存下一个节点。struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! NULL) { struct ListNode* next cur-next; // 先保存下一个不然断了就找不回来 cur-next prev; // 当前节点掉头指向前一个 prev cur; // prev前进 cur next; // cur前进 } return prev; // 最终prev就是新的头 }这里最关键的是一行struct ListNode* next cur-next;。如果不先保存执行cur-next prev之后原来的cur-next就丢了链表从中间断成两截。这个错误我见过太多次了错误代码写出来是好看的跑起来就完蛋。递归写法理解起来更难但代码极短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这一行——它在把后一个节点的指针掉头指向当前节点。初学递归时不用强行理解所有细节先照着写画图走几遍慢慢体会。2.3 快慢指针类中间的数学原理快慢指针的典型应用有三个找中间节点、找倒数第K个、检测环形链表。找中间节点的代码非常短struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这个代码为什么能得到中间节点因为慢指针走一步时快指针走两步快指针到达末尾时慢指针恰好走了一半路程。有一点要注意偶数节点个数时这个写法返回的是靠右的中间节点。比如4个节点slow会停在第三个节点。不同题目对返回位置的要求不一样需要根据题意调整。环形链表的检测思路是快指针每次走两步慢指针每次走一步如果链表有环快指针迟早会追上慢指针两者相遇。bool hasCycle(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }为什么一定能相遇想象两个人在环形跑道上跑步一个速度快一个速度慢速度差固定快的迟早会从后面追上慢的。至于为什么快指针要一次走两步而不是三步、四步因为两步可以保证每一步两个指针的距离变化为1不会出现跨过对方没碰到的情形。这个数学原理在进阶题“找到环的入口”里会更清晰。设链表起点到环入口的距离为a环的长度为b。快慢指针相遇时慢指针走了s步快指针走了2s步两者路程差为s这个s必然是环长b的整数倍因为快指针比慢指针多走了若干圈。所以slow s kb。此时你让一个指针从链表头重新出发另一个指针从相遇点出发两个都每次走一步。从头出发的指针走a步到达环入口时从相遇点出发的指针也走了a步。因为相遇点在环上的位置是s mod b 0即相遇点就是环入口的等价位置所以它走了a步后也到达环入口两指针必然在入口相遇。这个结论就是环形链表II这道题的解法基础。2.4 合并与相交类哨兵位与步数对齐合并两个有序链表我会用哨兵位 尾插法来实现。思路很直接同时遍历两个链表谁小就接谁最后把剩下的部分整体拼上去。struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); 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; struct ListNode* ret dummy-next; free(dummy); return ret; }这个题在初阶阶段必须达到闭眼能写的程度因为它是很多分治算法的基础比如链表的归并排序就要用它做合并步骤。相交链表这道题非常巧妙它要求找两个链表第一次相交的节点。最直观的解法是哈希表遍历A链表把所有节点地址存起来再遍历B链表第一个在哈希表中出现的节点就是交点。但更符合链表思维的解法是两个指针的“步数对齐”struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { if (headA NULL || headB NULL) { return NULL; } struct ListNode* pA headA; struct ListNode* pB headB; while (pA ! pB) { pA (pA NULL) ? headB : pA-next; pB (pB NULL) ? headA : pB-next; } return pA; }它的原理是如果A链表的长度为a mB链表的长度为b m其中m是公共部分的长度。pA走完A再走B总路径长是a m bpB走完B再走A总路径长是b m a两者相等。这意味着两个指针在第二次遍历时一定会同时到达交点。如果两个链表不相交它们会同时走到NULL循环自然退出。2.5 进阶类值得知道的几道题初阶阶段的链表题里有几道题可以作为进阶挑战学有余力时看看会有很大收获。“复制带随机指针的链表”是经典的中等偏上题目。它的难点在于每个节点除了next指针外还有一个random指针直接深拷贝时random指向的节点可能还没创建。常规解法是用哈希表建立原节点和新节点的映射关系第一遍遍历创建新节点并记录映射第二遍遍历根据映射设置random。还有更进阶的O(1)空间做法在原链表的每个节点后插入一个拷贝节点然后利用原节点的random来设置拷贝节点的random最后分离链表。这个做法不要求初阶掌握但能锻炼对链表结构的理解。链表排序也是进阶重点。数组排序可以直接用下标访问链表排序最稳定的思路是归并排序——先找到中点拆成两半递归排序再合并。你会发现快慢指针和合并有序链表这两个技能在这里全部用上了。3. 从一道题到一类题三种可以迁移的思路3.1 反转链表是一块万能积木反转链表为什么是核心因为它的变换能力太强了。判断回文链表常规做法是先用快慢指针找到中点然后把后半部分反转再从前半部分头节点开始同步比较。这个题把“快慢指针找中点”和“反转链表”两个技巧组合在一起解出来了会很有成就感。再看“反转链表II”它要求反转从第m个节点到第n个节点之间的部分。这个题不是无脑全反转而是要先定位到m位置的前驱然后对局部做反转。我实际做的时候发现把第m个节点的前驱记为pre然后从第m个节点开始执行m到n之间的反转逻辑边界条件非常容易错。一个小技巧是把pre-next一直指向新反转后的头节点同时用一个cur指针指向原始的第m个节点因为反转完之后这个cur应该成为局部链表的尾节点它的next要接上第n1个节点。3.2 快慢指针的适用范围比想象中大快慢指针不只能找中点和检测环它还能用来找链表倒数第K个节点。思路是快指针先走K步然后快慢指针同步走快指针到末尾时慢指针指向的就是倒数第K个。这个思路本质上也可以理解成“用快指针制造一个长度为K的窗口”让窗口整体滑动到链表末尾。快慢指针的升级应用是“重排链表”。题目要求把L0 - L1 - ... - Ln-1 - Ln重排成L0 - Ln - L1 - Ln-1 - L2 - Ln-2 ...。做法是先找到中点把后半部分反转然后交替合并两个链表。这里每一步都是前面讲过的内容但组合起来题目难度立刻上了一个台阶。我的体会是初阶阶段不一定要把这种题做出来但至少要有“拆解成多个已知步骤”的意识这样刷题才会有积累感。3.3 哨兵位在什么地方都管用哨兵位除了用在删除和合并外在“分隔链表”“链表排序中合并两个已排序链表”等场景里也很管用。比如给出一个链表和一个值x要求将所有小于x的节点放在所有大于等于x的节点之前。这时候你可以开两个哨兵位节点一个挂接小于x的节点一个挂接大于等于x的节点遍历结束后把两个链表拼接即可。整个过程把头节点的动态变化全部隐藏了代码干净的让你怀疑是不是在写链表题。我的建议是从初学阶段开始每周挑一道用哨兵位的题目练手直到形成条件反射——“这道题的头节点可能变吗可能变就加哨兵。”一旦形成这种条件反射你在OJ上的通过率会有一个明显的跃升。4. OJ提交时的常见报错与排查套路4.1 空指针解引用链表题最常见的报错就是“访问了空节点的成员”编辑器或OJ给的提示通常是Segmentation fault或者空指针异常。我见过的最典型错误是删除节点时没判断当前节点是否为空直接cur-next-val当cur-next是NULL时就炸了。还有一个隐蔽的场景使用快慢指针时fast-next-next。如果fast-next本身是NULL访问fast-next-next就会出问题。所以代码里while (fast ! NULL fast-next ! NULL)这个判断顺序是有讲究的先判断fast不为空才能访问fast-next判短路的保证了第二个条件只在第一个条件成立时才会执行。4.2 死循环链表题死循环的常见原因是反转链表时没有把最后一个节点的next改成NULL。举个具体场景反转时cur-next prev遍历结束后prev指向原链表的最后一个节点cur指向NULL。如果中间某个节点没有正确断开原来的连接链表就会形成一个环OJ提交直接超时。另一个死循环场景发生在快慢指针里。如果你把快指针更新写成fast fast-next; fast fast-next;而不是合并成fast fast-next-next需要考虑两步之间的空指针判断。一旦跳出循环的条件写错比如只判断了fast ! NULL而没判断fast-next ! NULL就可能死循环。排查死循环的一个好办法是加打印语句。在循环里打印当前节点的值如果发现某个节点反复出现基本就是环形成了。4.3 返回的头节点不对删除类题目如果不用哨兵位很容易在头节点被删除后返回一个失效的指针。举例删除头节点时如果你只是把head往后挪了却没有更新返回值或者更新了但后续函数里又使用了旧的head指针就会出错。我在实际调代码时发现一个很反直觉的现象有时候本地运行结果是正确的但OJ上就是不过。排查了半天发现是函数返回的头节点没有更新到全局变量里。链表题里如果你在子函数里修改了头节点要么通过返回值传出去要么传入二级指针否则外层函数拿到的永远是旧指针。OJ题目一般只要求返回新头节点所以用返回值就行。4.4 内存泄漏和悬垂指针OJ平台一般不会因为内存泄漏扣分因为进程跑完就回收了。但如果你在面试或本地调试时被问到最好具备这个意识。内存泄漏的典型场景删除节点时只改了前驱的next却没有free掉被删除的节点。这在OJ上可能不会报错但内存消耗会变大。悬垂指针的典型场景是先free了一个节点但还有一个指针指在它上面之后又通过这个指针访问数据。这就是未定义行为运气好没事运气不好直接崩溃。我的习惯是free掉一个节点后立刻把相关的临时指针置为NULL防止误用。4.5 调试三板斧链表题的调试我总结了三个非常实用的方法。第一小规模用例。不要一上来就构造十几二十个节点的链表去调试只用两三个节点的链表在纸上把每一步的指针变化写出来。第二打印中间状态。在关键节点打印当前节点值和当前指针地址观察是否符合预期。比如反转链表时在循环里打印prev-val、cur-val、next-val很快就能定位是哪里断开的。第三画图。这看起来是老生常谈但链表题里它真的比任何调试工具都管用。每一步画一下图指针关系一目了然比盯着代码猜要高效一百倍。5. 刷题顺序与现场考试的注意事项5.1 给初学者的刷题节奏链表OJ题忌讳一上来就挑战最难的也忌讳只做最简单的。我给学弟学妹们推荐一条相对平滑的路线你可以参考第一步先做删除类。移除链表元素、删除排序链表中的重复元素、删除链表的倒数第N个节点。这个阶段目标只有一个理解前驱指针学会用哨兵位。第二步做反转类。反转链表迭代和递归都要会、反转局部链表。这个阶段目标是把三指针反转练成肌肉记忆。第三步做快慢指针。链表的中间节点、环形链表、环形链表II。这个阶段需要理解数学原理如果只记住代码不理解推导下次换一个问法还是会卡住。第四步做合并与相交。合并两个有序链表、相交链表、两两交换链表中的节点。这个阶段会发现前面练的哨兵位、双指针技巧开始产生复利效应。第五步挑战综合题。回文链表、重排链表、链表排序。这些题目本身有一定难度但拆开来看每一块都是前面练习过的内容。5.2 时间分配的一个实际建议如果是准备期末考试或初阶机考不需要追求刷太多题。把上面列出的核心题每种类型挑两道总计十道左右反复做到不看答案能写出来效果远好于看完五十道题的解体思路却不自己动手。我自己带过的学生里进步最快的做法是每天只刷一道链表题但要把这道题做完所有变体。比如今天做反转链表就把迭代、递归、反转局部三个变体全写一遍。这样一周下来链表题的基本功就非常扎实了。考试前一周再用OJ平台自带的模拟测功能把常见题型过一遍重点测试边界条件处理。我发现很多人不是不会写而是考试时一紧张就忘了链表可能为空、头节点可能变这种基本前提最后挂在最简单的用例上。5.3 面试场景下的链表题要求如果是准备面试链表题的要求会比机考高一个档次。面试官看的不只是答案正确更看重你分析问题的思路和边界意识。我建议在面试前专门练习“白板写链表题”不用编辑器只用纸和笔。这听起来很像老古董但实际训练效果很好因为你不能在编译器的提示下发现问题必须在写之前就把所有边界条件想清楚。面试时如果做到“先画图、再讲思路、最后写代码”这个流程即使最后代码有小瑕疵面试官通常也会认可。另一个面试里常问的问题是时间复杂度和空间复杂度。链表题里的快慢指针、反转、合并都要能说清为什么是O(n)时间、O(1)空间哪些做法虽然简洁但额外用了O(n)空间。比如相交链表用哈希表是O(n)空间双指针法就是O(1)空间环形链表II用哈希表是O(n)空间快慢指针是O(1)空间。这些对比最好自己做一个笔记临场才不会卡壳。我个人在实际操作中最大的体会是链表OJ题最大的障碍从来不是语法而是缺少“边界感”。只要每次写代码前逼自己画一张图、想清楚空链表和单节点的场景就已经比绝大多数人做得好。最后再分享一个小技巧——刷链表题时准备一个固定的草稿本把每道题的指针变换图画在旁边隔天复习时看一眼图就能快速回忆起解法。这个习惯我保持了整个初阶学习阶段后续学二叉树、图结构时这种“先画图再写代码”的习惯也一直在帮我的忙。