链表这东西说难不难说简单也真不简单。我在带新人刷题、帮朋友准备面试的过程中发现很多人二叉树、动态规划都能聊两句一碰到链表的指针操作就翻车——空指针判断漏了、头结点丢了、循环链表死循环了。这篇就想把C里链表算法练习的完整路径梳理一遍从环境准备、基础操作到面试高频题再到真正调试排错的过程全程使用C实现所有代码我都在VSCode里实测跑过。适合谁看两类人。一是刚学完C语法、想开始刷数据结构的初学者这篇文章能帮你把单链表、双链表、循环链表的基本功打牢搞清楚指针和引用在链表操作里怎么用。二是准备面试的求职者里面涵盖了插入、删除、反转、快慢指针、归并排序等高频考点每个题我都写了相对完整的实现和复杂度分析可以直接当复习提纲用。1. 系列定位为什么第二个专题选链表我的“C算法练习”这个系列第一个专题写的是复杂度分析与暴力枚举优化当时很多人留言问什么时候上数据结构。数据结构里第一个该练的其实不是数组——数组太直白了真正让你建立起“指针操作”感觉的就是链表。链表的题有一个特点代码量往往不大但边界条件特别多。插入一个节点要考虑空链表、头插、尾插、中间插删除一个节点要考虑删头、删尾、删中间、删唯一节点。这些边界在面试里都是送分题也是送命题——少一个判断整个程序就崩。C里链表操作还涉及手动内存管理写完了还要想着delete这比Java、Python那种自动回收的环境多了一层考验。从算法思维养成的角度讲链表是训练“循环不变量”和“指针思维”的最佳载体。你写一个while循环遍历链表循环里要保证什么p指针不为空、p-next可以安全访问、prev和cur的相对位置始终正确。这些看似琐碎的约束其实就是后面写复杂算法时的基本功。我常说链表题做得好的人写二分查找、写归并排序的边界处理也不会差因为核心能力都是一样的把每一行代码执行时程序的状态想清楚。2. 环境与牛刀小试VSCode里把C跑起来很多人死在第一步——环境没配好。我推荐的是VSCode MinGW-w64这套组合免费、轻量、跨平台调试功能也够用。配置的时候有几个坑必须说清楚。2.1 编译器安装与路径配置去MinGW-w64的官方源下载安装包安装时x86_64架构、win32线程模型、seh异常处理模型这三个选项别选错。装完之后把bin目录比如C:\mingw64\bin加到系统PATH里然后打开新的终端窗口执行g --version能输出版本号就是装好了。如果提示“g不是内部或外部命令”大概率是PATH没生效要么重启终端要么检查路径是否正确。VSCode里需要装C/C扩展这是微软出的那个装完会自动识别编译器。然后在项目根目录建.vscode文件夹里面放三个文件tasks.json负责编译launch.json负责调试c_cpp_properties.json负责智能提示。我的tasks.json关键配置长这样{ version: 2.0.0, tasks: [{ label: g build, type: shell, command: g, args: [ -g, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ], group: build }] }注意那个“-g”参数生成调试信息用的不加的话断点都不好使。2.2 第一个链表程序建立与遍历环境好了先用一个最小程序验证一下手感。定义一个单链表节点结构体写一个尾插函数再遍历打印#include iostream struct ListNode { int val; ListNode* next; explicit ListNode(int x) : val(x), next(nullptr) {} }; // 尾插法返回新的头结点 ListNode* append(ListNode* head, int value) { ListNode* newNode new ListNode(value); if (head nullptr) { return newNode; } ListNode* temp head; while (temp-next ! nullptr) { temp temp-next; } temp-next newNode; return head; } // 遍历打印 void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { std::cout cur-val - ; cur cur-next; } std::cout nullptr std::endl; }这里有个细节特别值得跟新手强调为什么要返回新的头结点因为空链表时你new出来的节点就是要返回的头结点。如果你把head当参数传进去改那必须用指针的指针ListNode**或者引用ListNode*否则函数里改了外面不知道。很多初学者就在这里晕。我建议一开始统一用“返回新头结点”这种写法不用引用不用二级指针逻辑最直白。等练熟了再学ListNode*那种写法能少写点代码。int main() { ListNode* head nullptr; head append(head, 1); head append(head, 2); head append(head, 3); printList(head); // 释放内存 ListNode* cur head; while (cur ! nullptr) { ListNode* tmp cur-next; delete cur; cur tmp; } return 0; }运行结果1 - 2 - 3 - nullptr看到这个输出算是正式入门了。3. 单链表核心操作把增删查练成肌肉记忆链表的操作看起来多实际上就是几个固定套路找前驱、断链、接链。下面这些函数我建议每个都亲手写三遍以上直到不用看参考代码就能默写出来。3.1 按位置插入带头结点与不带头结点的区别这是相关热词里出现频率很高的问题也是面试最容易考的。不带头结点的单链表空链表和非空链表的处理逻辑不一致插入位置的边界情况特别多。带头结点的链表头结点是哑结点dummy node不存实际数据真正的数据从第二个节点开始这样所有插入操作都统一了。看我写的不带头结点版本的按位置插入用“虚拟头结点”技巧规避掉头插的特殊情况// 在指定位置pos插入节点pos从0开始计数0表示头插 ListNode* insertAtPos(ListNode* head, int pos, int value) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; ListNode* cur head; int index 0; while (cur ! nullptr index pos) { prev cur; cur cur-next; index; } if (index ! pos) { // 位置不合法pos超过了链表长度 std::cout insert position out of range std::endl; delete dummy; return head; } ListNode* newNode new ListNode(value); prev-next newNode; newNode-next cur; head dummy-next; delete dummy; return head; }核心逻辑来一个虚拟头结点省掉了“如果pos等于0head要不要变”这种判断。prev永远指向待插入位置的前一个节点只要维护好prev和cur的相对关系插入的代码就只有那两行。位置合法性的判断也不能省index ! pos说明链表走完了还没到目标位置此时要报错返回。3.2 删除指定值的节点删除的核心是找到待删节点的前驱。常规写法需要单独判断头结点是否要删用虚拟头结点同样能统一ListNode* removeByValue(ListNode* head, int value) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; ListNode* cur head; while (cur ! nullptr) { if (cur-val value) { prev-next cur-next; delete cur; break; } prev cur; cur cur-next; } head dummy-next; delete dummy; return head; }注意这个版本只删掉第一个匹配到的节点如果要删除所有匹配的节点那循环里就不能break而且删除后cur要指向prev-next防止cur变成悬空指针。这个细节是常见面试追问点建议自己改一改试试。这里额外提醒一句C特有的问题delete之后那个指针还在但它指向的内存已经还给系统了绝对不能再去访问。如果函数的其他逻辑还需要用到这个节点的数据那就先存一份再删。很多C内存错误就是这么来的——double free或者use after free那可比结果算错难排查多了。3.3 反转链表迭代与递归双写法反转链表是链表题里的“hello world”但真要白板写干净也不容易。迭代法是最容易理解的维护三个指针prev、cur、nextListNode* reverseListIterative(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 先保存下一个节点 cur-next prev; // 反转指针 prev cur; // prev前移 cur next; // cur前移 } return prev; // 新的头结点 }这四行是核心每行顺序都不能乱。你可以画图验证一下某一步如果把cur-next改了却没用tmp保存原来的next那整个链表就从中间断开了后面的节点全找不回来。递归版难想一点但代码更短ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }递归的理解要点是递归函数返回的是“以当前节点为起点的子链表反转后的新头”。当你在某个节点上假设后面的都已经反转好了你只需要让当前节点的下一个节点指向自己再断开自己跟原来的下一个节点之间的连接。这个思路其实挺难的我第一次学的时候画了半小时图才想通。但想通之后对递归的理解会提升一个层次。3.4 链表的中间节点快慢指针的入门找链表的中间节点不用先遍历一遍数长度再走一半快慢指针一次遍历就够了ListNode* middleNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }slow每次走一步fast每次走两步当fast走到尾时slow正好在中间。偶数个节点时返回的是靠右的那个中间节点具体取决于题目要求。快慢指针这套路往深了走就是链表判环、找环入口、求链表交点等一系列问题的基础。把中间节点这道题弄明白后面就顺了。4. 环形链表从判环到找入口面试里链表模块的高频压轴题环形链表系列绝对算一个。跟着网上那些热词里的“链表遍历”、“循环单链表”往下抠最终都会遇到这个方向。4.1 判断有没有环思路还是快慢指针——如果有环fast一定会在某次循环中追上slow而且不会出现fast直接跳过slow的情况因为在每次迭代里它们的相对距离只会减少1bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }这个写法有个关键点判断相遇要在指针移动之后做因为初始时slow和fast都指向head如果先判断就误判成有环了。4.2 找出环的入口节点更难一点的是求出环的入口。数学推导过程是这样的设头结点到环入口的距离为a环入口到相遇点的距离为b相遇点继续走到环入口的距离为c那么环的周长就是bc。slow走了abfast走了abk(bc)又因为fast的路程是slow的两倍所以有abk(bc) 2(ab)化简得到 a k(bc) - b。当k1时a c。这意味着从相遇点出发走c步回到入口从头结点出发走a步也到入口。由于ac所以让两个指针分别从头结点和相遇点出发都每次走一步它们一定在环入口相遇。写成代码ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode* ptr1 head; ListNode* ptr2 slow; while (ptr1 ! ptr2) { ptr1 ptr1-next; ptr2 ptr2-next; } return ptr1; } } return nullptr; }这个公式推导建议自己拿纸走一遍遇到一个带环的例子手动推一遍。面试问到这题时能把数学原理讲清楚的候选人印象分会好很多。5. 合并与排序绕不开的进阶进阶题单链表练熟之后可以上点强度了。合并两个有序链表和链表排序是综合了指针操作、递归或迭代逻辑、复杂度分析的典型题目。5.1 合并两个有序链表LeetCode第21题解法很多我推荐递归实现代码非常优雅ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 nullptr) return l2; if (l2 nullptr) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }理解的角度是mergeTwoLists(l1, l2)返回的是合并后链表的新头。如果l1的头更小那么新头就是l1接下来只需要继续合并l1-next和l2。这本身就在原节点上拼接没有新建节点空间复杂度O(1)递归调用栈不算。如果你对递归的栈深度不放心可以改迭代版思路就是维护一个dummy头和cur指针哪个小接哪个。5.2 链表归并排序相关热词里有“归并排序算法”链表版的归并排序也是面试常客。数组归并排序好写链表归并排序的难点在于怎么找到中点怎么断开怎么合并步骤拆开就清晰了。先找中点分成两半用之前练过的快慢指针。然后递归排序两半。最后用mergeTwoLists合并ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* slow head; ListNode* fast head; ListNode* prev nullptr; while (fast ! nullptr fast-next ! nullptr) { prev slow; slow slow-next; fast fast-next-next; } prev-next nullptr; // 断开左半部分和右半部分 ListNode* left sortList(head); ListNode* right sortList(slow); return mergeTwoLists(left, right); }注意那个prev指针它指向slow的前一个节点用来把链表从中间切断。如果不切断左边的递归排序会访问到右边的节点结果完全乱掉。这个细节我见过好几个人卡住。时间复杂度稳定在O(n log n)空间复杂度不考虑递归栈是O(1)不是数组归并那种O(n)这也是链表归并排序的优势。相比之下如果让你用快速排序做链表交换节点的操作要复杂得多partition的写法也很别扭所以链表现实中更倾向于归并。5.3 两个链表的第一个公共节点这也是个高频题两个链表在某个节点之后完全重合。思路非常巧妙用两个指针分别从两个链表头出发走到末尾后跳到另一个链表的头继续走。因为两个指针走过的总长度最终相等所以它们一定会在第一个公共节点相遇或都走到nullptrListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; }这里的关键是处理“不存在公共节点”的情况两个指针都走完本链表一遍再加另一链表一遍最终同时等于nullptr循环退出返回nullptr逻辑天然正确。这个思路我愿称之为“链表版龟兔赛跑”学完之后你会觉得写算法的乐趣很多时候就来自于这种巧妙设计。6. 双链表与循环链表别被“变种”吓住很多人练单链表练到飞起一看到双链表和循环链表就发怵其实原理是完全一样的只是多了一个指针要维护或者多了一个边界条件。6.1 双链表的三指针操作双链表的节点长这样struct DoublyListNode { int val; DoublyListNode* prev; DoublyListNode* next; explicit DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {} };插入操作比单链表多一个步骤不仅新节点的next要指向后继新节点的prev要指向前驱后继节点的prev也要回指新节点。四个指针赋值顺序不能乱。我的口诀是先把新节点的两个指针接好再拆旧链也就是先改变跟新节点直接相关的指针再去动旧节点的指针。6.2 循环链表的遍历终止条件循环单链表没有nullptr作为终点遍历终止条件是cur-next head。判断是否到达结尾要用temp的next是否等于头结点而不是temp本身是否等于nullptr。这个区别如果不适应写着写着就会陷入死循环。我推荐的遍历写法是do-while因为循环链表至少有一个节点do-while先执行再判断天然适配void printCircularList(ListNode* head) { if (head nullptr) return; ListNode* cur head; do { std::cout cur-val - ; cur cur-next; } while (cur ! head); std::cout (back to head) std::endl; }这个写法不踩坑也不用额外的哨兵节点判断。实际项目里循环链表通常配合一个tail指针使用让尾插变成O(1)操作很实用。7. 实操问题排查实录链表调试的野路子我写链表题这几年遇到过的程序跑挂情况加起来比头发还多。每次帮人看问题翻来覆去就那么几个典型毛病。整理成一个速查表症状常见原因排查方法程序崩溃/段错误访问了nullptr的next成员先检查while条件里有没有判空链表丢失一半节点指针覆盖前没有保存next检查是否需要临时变量暂存死循环跑不完循环链表没有终止条件加计数器打印或问自己遍历终点是什么打印结果有垃圾值节点未初始化或结构体构造函数缺失用构造函数初始化所有成员重复释放内存崩溃多个指针指向同一节点delete了两次每次delete后把指针置nullptr反转后链表丢失反转时指针顺序错误画图验证逻辑或调试器逐步单步7.1 VSCode调试器的正确打开方式有很多同学问我调试技巧我强烈建议在VSCode里用调试器而不是到处加cout。单链表指针的指向关系用调试器的Watch面板观察一目了然。设置断点后在Watch里输入cur和cur-next右键选择“Hex Value”可以看到地址对比一下两个地址的差值就知道是不是next指向了错误的位置。还有个小技巧遇到链表循环或者丢失节点时我会在关键循环里暂停后手动把整形数字放入Watch比如“head”和“cur”的地址再输入表达式“cur head”得到一个布尔值来判断循环是否绕回了头节点。比人脑去推快得多。7.2 内存泄漏的检测与规避C链表操作是有“自己的债”的new出来的每个节点都对应一次delete。最简单的方法是写一个专门的释放函数因为在main的末尾统一释放不如写一个工具函数每次测试完直接调用。我习惯在测试链表程序时在main函数开头放一个总节点计数变量new和delete的时候手动更新。如果是实践项目推荐直接用ValgrindLinux或Dr. MemoryWindows检测内存泄漏。VSCode里也能装C/C插件自带的内存检查工具不过配置稍微有点麻烦等你们做到复杂项目再上不迟。8. 面试级提分点从会写代码到讲清楚逻辑前面这些内容足够你应付大多数链表笔试了。但如果目标是面试还得再进一步——不仅要写出来还要能边说边写讲清楚每一步为什么这么做。8.1 复杂度分析的几种口径链表题的时间复杂度好分析最常见的三个复杂度级别遍历一遍是O(n)双指针一次遍历也是O(n)注意常系数更小但量级不变归并排序O(n log n)。空间复杂度要特别注意递归版本的调用栈反转链表的递归版空间复杂度是O(n)因为递归深度是n迭代版才是O(1)。这个区别面试官几乎必问。时间复杂度分析时有人问什么时候用O什么时候用Θ其实在链表场景里基本不用纠结我们算的都是最坏情况下的渐近紧界既可以用Θ(n)也可以用O(n)只是表述习惯不同。面试时用O(n)不会扣分说清楚是最坏情况即可。8.2 面试官最爱的六个追问拿反转链表举例面试官可能顺藤摸瓜式追问我总结过高频追问套路能不能用递归实现空间复杂度多少能不能反转链表的一部分从第m个到第n个每k个节点一组反转最后不足k个保持原样怎么做找中间节点时偶数个节点返回哪个怎么改成另一个快慢指针判环的原理是什么为什么fast每次走两步而不是三步如果链表非常长递归会爆栈吗怎么避免这些问题都能从本文前面讲的内容延伸出来。我的建议是真的拿笔把这些变种都写一遍写不出来就回头看看前文的代码直到每个变体都能顺手写出来。8.3 养成三个代码习惯写链表题的代码时有习惯一能不修改输入链表就不修改如果要修改先跟面试官确认。习惯二凡是改变了链表结构的函数要么返回新的头结点要么用引用或二级指针改参这能避免一大类调用方的困惑。习惯三写完代码立刻检查空链表、单节点链表、头尾操作这三种边界场景把测试用例在脑子里跑一遍再交卷。这三个习惯能帮你减少七成以上的低级错误。我带过的实习生里后面追评比较好的那几个全都是认真养成了这些习惯的人。9. 热词乱炖从搜索关键词看新人最常卡在哪每次写完技术主题我都会顺带看看大家搜索最多的关键词这其实是很好的“学情”反馈。这次标题相关的热词里有些信息量很大。9.1 “不带头结点的单链表” vs “带头结点的单链表”这个搜索热词说明很多人在课程作业或考试题里遇到了这个对比。我的建议很简单如果题目没有明确要求“不带头结点”一律选择带头结点实现因为代码统一性好、边界少。如果题目明确要求不带头结点就用虚拟头结点技巧dummy node把逻辑统一起来前面已经演示过。面试手写时也建议用dummy node代码短、逻辑清楚面试官也认可。9.2 “c结构体链表基本语法” 与 “单链表基本操作实验”这两个关键词指向的是同一个群体——还在起步阶段的初学者。你们的困惑通常是结构体里能放自己类型的指针吗能这叫“自引用结构体”因为这里存的是指针而不是结构体对象所以编译器可以确定大小。这是链表能存在的基础。给初学者的实操路线先在纸上画出链表结构图把每个节点的指针箭头画明白然后再开电脑写代码。我听很多ACM选手说过他们入门链表时也是看了几十张图解才想明白的。不要急链表练的就是这份空间想象力。9.3 “c 前缀和”、“kmp算法”与链表的关系搜索词里还混着“前缀和”“KMP算法”这些词这些跟链表本身无关但它们反映了一个现象大家按系列刷题时会顺着知识树一路搜下去。链表是数据结构这条枝干上的基础节点前缀和属于数组技巧KMP属于字符串匹配这几块的知识体系是互相独立的但它们的共同底层是“指针/索引的维护”和“状态转移”的思路。所以我更建议大家把链表当成“指针思维的训练场”练熟之后再碰KMP这类抽象算法理解速度会快很多。别一上来就啃硬骨头数据结构的学习顺序很重要。10. 从单链表起步再往双链表和题目变体延伸到这里C链表算法的核心玩法基本上都覆盖了。最后想聊聊怎么把单链表的代码技巧迁移到双链表和其他变体上这也是我最近带新人时总结出来的进阶路线。10.1 双链表不是“另一种链表”而是“加了一个指针的单链表”很多人会从单链表直接跳到双链表然后被捣腾不清。我的理解是双链表就是在单链表每个节点上新增一个prev指针操作原则“先补新节点的关系再拆旧节点的关系”和单链表完全一致。只要单链表的增删改查练熟了双链表只是多写几行代码而已。10.2 LRU缓存是双链表的经典实战如果你想知道双链表到底有什么用直接去看LRU缓存算法题。它要求put和get都是O(1)方法就是哈希表双链表。哈希表负责快速定位节点双链表负责维护访问顺序。这道题进可考察工程能力退可考察数据结构基本功值得一刷。我刷这道题时的经验是先不要一上来就写代码。先用双链表画一个“访问顺序”的演示图再讨论哈希表怎么映射到链表节点地址。逻辑通了代码就是照着填空而已。10.3 后续可以尝试的变体题终极建议的练习顺序是单链表反转 → 两两交换相邻节点 → K个一组反转链表 → 复制带随机指针的链表 → LRU缓存。这几道题难度渐进覆盖了链表题的基本套路。“复制带随机指针的链表”尤其有意思它考察的是“先复制主干再处理额外指针”的空间换时间思想解法不唯一有O(n)时间和O(1)空间的原地复制法也有一遍哈希表辅助的直接复制法。建议两种都写一遍体会两种思路的差异。链表题的乐趣就在于同一个问题可以有多种不同的“拆法”每一种拆法想通了你对指针和内存的理解就深沉一层。