刷LeetCode HOT 100的链表题很多人当初劝我别用C语言没有现成的容器、没有标准库帮你处理节点、连初始化一个链表都要手写一二十行。但刷完这二十几道题之后我想说——恰恰因为C语言什么都不给你你才被逼着把链表的每一个指针都看得明明白白。这篇博客是“Cs Log”系列的第一篇记录我用C语言硬啃HOT 100链表题的完整过程怎么搭基础设施、核心题目怎么拆解、哪些坑我踩得最惨以及最后沉淀下来的模板和心法。如果你正准备刷LeetCode或者正在学C语言链表部分不知道怎么练手这篇文章都值得花十分钟看完。我不讲虚的全部是实际敲过、跑过、提交报过错之后的真实经验。HOT 100里的链表题看起来多其实归类之后根本不需要焦虑跟着我的分组和复盘节奏来你也能把这块硬骨头啃下来。1. 为什么选C语言刷链表题动机、准备与基础设施1.1 刷题语言选型背后的真实考量先交代一下背景。我当时的处境是C语言语法刚学完指针和链表这部分上课听得云里雾里结构体套结构体、指向指针的指针每次看都头大。想通过刷题巩固但栈和队列的题用C写起来太痛苦反而是链表——翻来覆去就是节点和指针特别适合用来把C语言的指针功底打扎实。很多人喜欢用Python、Java刷题因为它们有现成的链表实现和GC垃圾回收你根本不用关心内存释放。但这也带来了一个隐蔽的问题你会不知不觉忽略链表最核心的东西——指针的指向变化。用C语言刷链表题等于把“思考”和“落实”之间所有的缓冲都去掉了。你脑子里必须非常清楚当前指针指向哪个节点、操作完之后哪个节点的next被修改了。这个能力一旦练出来看很多C工程的源码都会觉得轻松很多。HOT 100里的链表题大概是这么个量级纯链表题大约有二十来道分布在反转、合并、相交、环形、删除、排序、复制等几个大类。数量不算多但覆盖了链表几乎全部的核心操作。用C语言把这些题刷完链表基本就算真正掌握了。1.2 一套趁手的C语言链表基础设施模板用C刷题有个现实问题LeetCode里人家已经把结构体给你定义好了比如struct ListNode但本地调试时你得自己写。为了避免每次开新题都重复造轮子我在“Cs Log”仓库里放了一个linked_list_base.h里面固定有这几样东西struct ListNode { int val; struct ListNode *next; }; // 根据数组创建链表带哨兵节点版本 struct ListNode* createList(int* arr, int size) { struct ListNode dummy {0, NULL}; struct ListNode* tail dummy; for (int i 0; i size; i) { tail-next (struct ListNode*)malloc(sizeof(struct ListNode)); tail-next-val arr[i]; tail-next-next NULL; tail tail-next; } return dummy.next; } // 打印链表 void printList(struct ListNode* head) { int count 0; while (head count 20) { // 防止环形链表导致死循环 printf(%d - , head-val); head head-next; count; } printf(NULL\n); } // 释放链表 void freeList(struct ListNode* head) { while (head) { struct ListNode* tmp head; head head-next; free(tmp); } }这套模板我用了整个刷题周期。注意几个设计细节createList里用了一个栈上哨兵节点dummy这样就不用为头节点的特殊情况单独写分支printList加了循环次数限制防止把环形链表打印到天荒地老freeList是先存tmp再移head再释放顺序不能反。这些细节看起来不起眼实际刷题调试时每一个都能救命。1.3 环境准备VS Code与编译调试本地调试我用的VS Code配C/C插件配合Code Runner一键编译运行。这里有个坑要单独说一下如果用Code Runner默认配置跑C程序它会用gcc file.c -o file这种方式编译如果你的代码里有两个.c文件比如主文件和链表基础模板需要手动配置args参数否则会报“undefined reference”。我的建议是直接用CMake或者一个简单的Makefile。刷题本地验证的场景不需要复杂构建系统一个build.sh脚本足够先编译基础工具文件再编译当前题目文件链接生成可执行文件。VS Code里配置好调试器之后断点打在指针操作那一行配合“监视”窗口看head、prev、tmp几个变量的地址和值的变化链路很快就清晰了。这一步非常值得做——很多人刷链表题只看代码想逻辑这很容易漏掉指针指向的细节问题。2. 链表题的核心套路指针操作、哨兵节点与快慢指针2.1 链表题的本质遍历、插入、删除三件套把HOT 100里所有链表题做完你会发现一个事实无论题目包装成什么样链表题的核心操作永远只有三个——遍历、插入、删除。反转链表本质是遍历时不断在头部插入合并有序链表本质是归并遍历加尾插删除倒数第N个节点本质是找到节点再删除两两交换节点本质是三步交换指针。想明白了这一点就抓住了链表题的“题眼”。做题时我习惯先问自己三个问题这道题要遍历吗要改指针吗是改多少个指针以删除倒数第N个节点为例它既需要找到目标节点遍历又需要把前一个节点的next指向后一个节点改指针。确定这两个动作之后再设计链表访问的顺序代码就不会乱。另一个常常被忽略的点是指针的“数量”。链表操作中改几个节点往往就需要几个指针变量来暂存。比如删除一个中间节点至少需要两个指针一个指向当前节点一个指向当前节点的前驱。而“两两交换”这种题需要三个甚至四个指针才能清晰完成。指针变量要敢声明别怕多怕的是想不清楚每个指针什么时候扮演什么角色。我自己的习惯是动手写代码之前先在草稿纸上把链表画出来用箭头标出每一步指针的变化。这个习惯帮我避免了大量无意义的debug时间。当你发现一次提交报错与其盯着代码猜不如在纸上把链路走一遍往往几秒钟就能看出问题所在。2.2 哨兵节点让头疼的边界条件直接消失边界条件永远是链表题的第一大失分点要删除的正好是头节点怎么办链表为空怎么办链表只有一个节点怎么办这些判断写起来又臭又长还容易漏。我的解决办法是引入哨兵节点dummy node。struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode dummy {0, head}; struct ListNode* slow dummy; struct ListNode* fast dummy; // fast先走n1步 for (int i 0; i n; i) { fast fast-next; } while (fast) { slow slow-next; fast fast-next; } struct ListNode* target slow-next; slow-next slow-next-next; free(target); return dummy.next; }上面是删除倒数第N个节点的标准解法核心就是用哨兵节点统一处理“删除头节点”这种特殊情况。如果没有dummy当链表只有一个节点且要删除倒数第1个节点时slow-next会变成野指针代码得多写好几行判断。加了dummy之后头节点也变成了一个普通节点所有删除逻辑统一走同一条分支。这个模式在反转链表有时用、删除排序链表中的重复元素、两两交换节点等题里都能复用。2.3 快慢指针链表题的“双人舞”快慢指针是链表题里最优雅的一个套路。环形链表检测141、返回环形链表入口142、找链表中点、找倒数第N个节点全部可以用快慢指针解决。它的思想很简单两个指针从同一起点出发一个每次走两步一个每次走一步如果链表有环它们一定会在某个地方相遇。为什么快指针每次走两步而不是三步因为两步保证慢指针进环后的第一圈内就能被追上不会出现刚好跳过相遇点的情况。这个细节如果自己推导一遍会记得很牢设环外长度是L环的长度是C慢指针进环时快指针已经在环里走了若干距离快指针相对慢指针每次多走一步最多走C-1步就能追上根本不需要走好几圈。环形链表II那道题还有一个数学结论相遇点到环入口的距离等于链表头到环入口的距离。很多题解直接甩结论让大家背我建议自己多画几次图推导理解了之后做题就不容易忘。3. HOT 100经典链表题逐题拆解3.1 反转链表206迭代与递归的AB面反转链表是HOT 100里被点名的“经典中的经典”也是我Cs Log里记录最详细的一道题。迭代写法核心是三个指针prev、curr、next每次循环里先把curr-next存到next然后把curr-next指向prev再整体右移。这个“先保存再断链”的顺序是灵魂很多人写错是因为直接让curr-next prev导致后面的节点找不到了。递归写法更短但理解成本更高struct ListNode* reverseList(struct ListNode* head) { if (!head || !head-next) return head; struct ListNode* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }递归的代码只有四行但你必须想清楚递归返回的是反转后的新头head-next-next head是把当前节点拼到已经反转好的链表尾部head-next NULL是让原来的头变成新的尾巴。两种写法的取舍可以参考下面这个表格写法时间复杂度空间复杂度适用场景迭代O(n)O(1)追求效率、代码可控时优先递归O(n)O(n)递归栈训练递归思维、代码简洁优先我建议两种写法都熟练掌握迭代用于追求效率和可控性递归用于训练递归思维。HOT 100里很多题都会衍生出反转链表的变体比如反转链表II、K个一组翻转链表掌握基础版是前提。3.2 合并两个有序链表21与两数相加2递归的妙用合并两个有序链表按迭代写法是典型的归并两个指针分别指向两个链表头谁小取谁然后移动指针。但我想重点说递归写法因为它是理解链表递归的绝佳例子struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }递归的终止条件是某一方为空直接返回另一方。这背后的逻辑是一旦有一方链表已经为空剩余的节点全部来自另一方不需要再比较了。每次递归选取较小的节点作为当前结果的头然后递归合并剩下的部分。这个写法写出来非常简洁跑测试也没有栈溢出风险链表长度有限值得反复品味。合并K个升序链表23虽然也是HOT 100里的重量级选手但它的核心还是复用mergeTwoLists用分治或者优先队列把多条链表两两合并思路是相通的。两数相加也是链表题里的高频题它的核心是模拟“竖式加法”。两个链表从左到右刚好对应数字的低位到高位我们只需要维护一个carry进位变量同步遍历两个链表取当前节点的值加起来再加进位val sum % 10carry sum / 10直到两个链表都为空且进位为0。这里有个容易漏掉的点当两个链表都遍历完了但进位还等于1时需要额外malloc一个新节点存放最高位的1。这道题很好地训练了“同时遍历两个链表”和“处理最后残留状态”的能力。3.3 环形链表141/142与相交链表160双指针的进阶玩法141题用快慢指针基本是标准答案。慢指针每次走一步快指针每次走两步如果相遇就说明有环。这里有个边界情况要小心快指针在走第二步之前必须先判空否则对空指针解引用直接内存错误。142题在141基础上多问了一个问题环的入口在哪解法是快慢指针第一次相遇后把一个指针移回链表头然后两个指针都以每次一步的速度前进再次相遇的位置就是环的入口。这个结论看起来很神奇其实推导一下就是数学题。我自己在日志里画了不下十张图才彻底理解建议你也画一画别死记结论。相交链表160更是把“双指针”发挥到了极致用两个指针PA、PB分别从两个链表的头出发PA走完A链表后跳到B链表头继续走PB走完B链表后跳到A链表头继续走如果两个链表相交它们一定会在第一个相交节点相遇。这个解法的精妙之处在于通过“互相换路”消除了两个链表长度差的影响。写完代码后我为这个解法拍了半天大腿忍不住在日志里写了一句“这才是优雅”。3.4 删除链表的倒数第N个节点19一次遍历就够了这道题前面展示过代码这里再说一下它的关键设计快指针先走n1步然后快慢指针同步走当快指针走到链表尾时慢指针正好停在倒数第N1个节点也就是待删除节点的前驱。先走n1步的原因是我们希望慢指针指到“待删节点的前一个节点”这样删除操作直接slow-next slow-next-next就可以。如果只先走n步慢指针会停在待删节点上删除时还得再维护一个前驱指针。这道题用C语言实现时一个容易出错的地方是for (int i 0; i n; i)循环里没有判空如果n等于链表长度快指针正好移动到NULL此时第二个while循环一次都不会执行删除的就是头节点而dummy.next保证了头节点被删后仍能正确返回新的头。没有dummy的话这里就是一个极易触发崩溃的场景。我从这道题开始真正建立了“凡涉及头节点可能变化的操作一律先加dummy”的习惯。4. 刷题日志里踩过的C语言链表坑4.1 free之后不置空悬空指针的教训C语言刷链表题内存管理绕不开。我第一次用C提交环形链表题时本地运行一切正常但提交到LeetCode却报错。排查了半天发现是本地调试时我在函数末尾释放了链表的全部节点但释放完之后没有把链表头置NULL。虽然LeetCode会自己管理测试用例的内存但我的本地测试代码里释放完节点后如果再次访问head-next就是一个典型的悬空指针——指针指向的地址已经被释放再访问就是未定义行为。这个坑的教训是每次free(ptr)之后马上补一句ptr NULL。从编译器到静态分析工具几乎所有的C语言规范都会强调这一点但实际写起来太容易忽略了。刷完链表题后我始终保持着对悬空指针和重复释放的警惕这些从竞争中练出来的习惯后来成了我写C工程代码时的基本功。4.2 头节点更新为什么必须用二级指针C语言刷链表题还有一个必须当面锣对面鼓说清楚的点什么时候要用二级指针struct ListNode**举例你要写一个“在链表头部插入一个节点”的函数。如果函数签名是void insertAtHead(struct ListNode* head, int val)那么函数里给head重新赋值不会影响外部调用者的head因为C语言是值传递函数内部改的只是形参的副本。头节点变化没法传出去这个函数就是错的。正确的做法是传指向头节点指针的指针void insertAtHead(struct ListNode** head, int val)函数内部用*head newNode来更新外部指针。LeetCode的题目为什么不用你传二级指针因为每道题的函数签名都设计好了比如返回struct ListNode*意思是“新链表的头节点由返回值带回”。但你自己设计辅助函数时一定要搞清楚“这个函数是否会修改头节点”。我早期写过一个反转链表的本地版本把辅助函数签名写错了跑了半天发现链表“原地没动”最后排查出是形参副本问题。这个经历让我彻底记住了指针传递的本质。下面这张表是我后来总结的从这里也一眼能看出最典型的几种内存问题问题类型典型场景规避方法悬空指针free之后又访问已释放内存free后立即置NULL形参副本辅助函数里要修改头节点传二级指针ListNode**内存泄漏本地循环跑测试用例用Valgrind检查lost情况4.3 LeetCode环境下的内存泄漏自己造的问题自己清理很多刚用C刷LeetCode的人会有一个疑问题解里经常看到malloc新节点到底要不要free答案是在LeetCode的评测环境里你的函数返回后整个进程就结束了操作系统会回收所有内存所以不free也能通过判题。但本地一遍又一遍地跑测试时内存泄漏会积累得肉眼可见——跑几十个用例后程序内存蹭蹭涨。我当时的习惯是写题解代码时专注算法逻辑不加free因为返回值里包含新链表free了反而没法返回但本地测试脚本里每次跑完一个用例会把测试链表和新生成的链表全部free掉。用Valgrind检查一遍没有内存泄漏才算这道题真正写完。Valgrind的输出里definitely lost、indirectly lost、possibly lost几类错误含义不同第一次看到时建议认真查一下比盲目改代码高效得多。4.4 边界条件漏判空链表与单节点链表链表题的边界条件真的是一门玄学。我第一次写“两两交换链表中的节点”时自信满满地写完空链表、单节点、双节点、三节点、四节点的本地用例全部通过结果一提交照样挂在一个很隐蔽的边界场景上。排查到最后发现我的循环条件里只判断了head和head-next但交换操作里有一处中间状态会访问cur-next-next当cur-next为NULL时就直接触发了段错误。这类错误靠肉眼很难看出来必须对每个可能为NULL的指针做一次“空指针审计”。我的经验是写完后先跑最小规模的边界用例——空链表、单个节点、两个节点。这三个用例能在5秒内暴露80%的指针错误。然后跑正常规模用例验证逻辑再跑大规模用例确认性能。这个顺序不要反否则排查起来非常痛苦。5. 从刷题到沉淀模板库与链表题的实战价值5.1 我整理的链表刷题自检清单Cs Log刷到最后我沉淀了一套“链表题自检清单”每次写完代码按清单逐项检查通过率明显提升检查所有能解引用的指针操作前是否保证它非NULL涉及头节点可能变化的操作是否优先用哨兵节点修改多个节点的next时是否用临时变量保存了会被覆盖的指针循环终止条件是否正确是否会死循环环形链表场景尤其注意链表的最后一个节点next是否置为NULL本地测试是否覆盖了空链表、单节点、两个节点的边界情况是否需要释放不再使用的节点是否在free后置空这个清单我现在还在用不只是刷题——日常写C语言相关代码时凡操作链表都会过一遍。它等于把C语言链表编程中的经典陷阱沉淀成了肌肉记忆这也算是我刷题过程中最值回票价的一部分。5.2 链表在实际工程中的用武之地有人会问刷完链表题除了面试还能干啥其实链表在真实工程里应用非常广。操作系统里的进程控制块队列、任务调度器、内存管理中的空闲块链表底层几乎都是用链表实现的。Linux内核代码里的list_head双向循环链表你在HOT 100的双链表题里学到的prev、next指针操作内核里都有对应。嵌入式领域的环形缓冲、最近最少使用LRU缓存淘汰策略LeetCode 146题本质也是哈希表双向链表的结构——146题正是HOT 100里最经典的链表综合应用题。刷完链表题后再去看这些工程场景你会发现书上的知识和真实世界之间从不缺联系缺的是那种“原来如此”的豁然开朗。这也是我坚持用C语言刷题的一个重要原因它逼着我在抽象算法与真实内存之间来回穿越建立的联系比用高级语言刷题要牢固得多。5.3 刷HOT 100的节奏建议最后分享一点刷题节奏的心得。HOT 100链表题看起来密集但不用怕。我按知识点分组刷先把反转链表三件套206、92、25放一起再把双指针题141、142、160、19、876放一组再把构建类题目21、2、23合并K个升序链表放一组。同一组的题解法套路相似刷起来有乘数效应第一道题花一小时第二道半小时第三道可能二十分钟就搞定。每次刷完一组我会把题号、考点、自己能想到的最优解思路、踩坑记录写进Cs Log。一周后再回头重新做一遍做错或卡壳的题检验是否真正掌握。这个“分组复盘”的节奏我觉得比每天随机刷两三道更高效也更容易坚持。用C语言刷链表题这条路走到最后你会发现最大的收获不是会了那二十几道题的解法而是终于能坦然面对指针和内存——很多C程序员工作好几年都没解决的心理阴影在这几十个小时的硬磕里被彻底治愈了。如果你也在刷题或者在学C语言的链表部分希望这篇日志能帮你少踩几个坑把链表这块硬骨头啃得更轻松一些。