不夸张地说链表几乎是每个学C的人都会在某个阶段卡一下的东西。数组用顺手了之后突然来了个需要手动申请内存、用指针串起来的数据结构很多人第一次看到Node* next这种写法的时候都会有点懵。我当年学的时候最直观的感受就是为什么要搞得这么麻烦直接开个数组不就行了这个疑问其实特别正常。等你真正理解了链表的工作原理再回头去看的时候你会发现它和数组之间的差别就好像排队买奶茶和拿号等叫号之间的差别。这一期就把链表这个东西从头到尾掰开揉碎讲清楚包括它到底解决了什么问题、节点结构怎么设计、增删查的核心操作怎么写以及链表在实际开发里最常见的几种玩法。文章里所有的代码我都会直接给出来配上详细的解释确保你照着敲一遍就能跑。1. 为什么数组用着舒服还要再学一个链表1.1 数组的硬伤插入和删除太折腾先想想数组是怎么存数据的。它在内存里是一块连续的存储空间就像一排编号固定的抽屉。这带来的好处很明显我想要第5个元素直接用下标arr[4]就能拿到时间复杂度是O(1)。这也是数组最让人舒服的地方——随机访问。但是代价在插入元素的时候就体现出来了。假设你在第二个位置要插入一个新元素为了保持数组的连续性你必须把原来从第二个位置开始的所有元素全部往后挪一格。如果是在数组头部做插入那就更痛苦了整个数组里的每个元素都要动一下。删除也是同理。删掉一个元素之后后面的所有元素都要往前挪一位把空位补上。挪动这么多元素是要花时间的在C里就是一次循环赋值。如果你在开发一个需要频繁在中间位置插入、删除数据的系统比如一个在线协作编辑器里维护操作记录用数组会导致大量的数据搬运性能会很差。1.2 链表换了个思路数据不连续靠导航串起来链表的核心思想就是不要求数据在内存里连续存放每个元素单独待在一个地方元素和元素之间用指针连接起来。打个比方。数组就像一栋公寓楼每个房间都是编好号的你按照门牌号就能直接找到人。链表则更像是一个寻宝游戏你要找到下一个人必须先见到当前这个人由他告诉你下一个人藏在哪里。每个人都只知道下一个成员在哪这就是链表的本质。正因为不需要连续内存链表在插入和删除的时候只需要修改几条指针的指向让新元素插队进来或者让某个元素退出。完全不需要搬运其他任何数据。这在需要频繁增删的场景下优势是压倒性的。当然链表的代价就是失去了随机访问能力。想找第10个元素你必须从头节点开始一个个跳过去。所以链表的查找是O(n)数组是O(1)。没有银弹数据结构本身就是各种取舍的结果。1.3 这一节的经验总结学链表之前先把数组和链表的优缺点对比记清楚。你只有在需要选型的时候才能做对决定。操作数组链表随机访问第i个元素O(1)O(n)头部插入/删除O(n)O(1)尾部插入O(1)需要维护尾指针才是O(1)中间插入/删除O(n)O(1)已知插入位置时内存空间连续、可能有浪费不连续、每个节点多存一个指针顺便说一句很多初学者有个误区认为链表一定比数组好。其实不是如果你大部分操作都是查某个下标的元素那数组是绝对的首选。链表只有在增删频繁、且不太关心随机查找的场景下才是优势局。2. 手写链表的第一步节点结构到底怎么定义2.1 节点就是最基础的积木块链表的最小组成单位是节点。每一个节点最少要包含两个部分数据域真正要存的数据可以是一个int一个string也可以是一个自定义的结构体。指针域存下一个节点的地址。用C定义一个最简单的单向链表节点通常是这么写的struct ListNode { int val; // 数据域存放实际数据 ListNode* next; // 指针域指向下一个节点 ListNode(int x) : val(x), next(nullptr) {} };我见过很多初学者在这里纠结为什么不能直接把整个节点嵌进来比如写成ListNode next;。你想一下如果你在结构体里直接放一个ListNode类型的成员那么这个结构体的大小就无限递归了它里面套了一个ListeNode这个ListNode里面又有一个ListNode……编译器直接报错。所以必须用指针。指针的大小是固定的在64位系统上是8字节它只负责记录下一个节点住在哪个地址而不是把下一个节点实体塞进来。这是一个经常会考的点一定要理解透。2.2 带头节点还是不带头节点这是一个问题很多教材会直接构造链表不搞头节点这东西。但在实际工程项目里或者说在刷力扣、做课程设计时你经常会看到带头节点的写法。这两个概念的区别很简单不带头节点第一个节点就是数据节点链表为空时head指针指向nullptr。带头节点链表的第一个节点是一个额外的哑元它的数据域不管它存在的意义是让链表永远有一个统一的入口。为什么需要头节点举个例子如果链表为空你想插入一个新节点那么不带头节点的写法必须单独处理修该head指针的情况。带了一个头节点之后链表永远非空至少有一个哑元所有插入删除的逻辑就不用特判开头了代码会简洁很多。我在自己的项目里如果链表的场景比较复杂一般直接用带头节点的模式。特别是单链表在中间做插入删除的时候带头节点能避免很多边界条件的坑。2.3 为什么要强调初始化构造函数注意上面我写了ListNode(int x) : val(x), next(nullptr)。这个构造函数的核心作用就是保证next初始化为nullptr。不初始化指针是一个常见的C陷阱。如果你直接写struct ListNode { int val; ListNode* next; };然后ListNode node; node.val 5;你的next成员就是一个未初始化的垃圾值。在Visual Studio的Debug模式下这个垃圾值经常是0xCDCDCDCD一旦你node.next-val程序直接崩溃。所以我的建议是只要是新手阶段手动创建节点的时候一定要养成初始化的好习惯能用构造函数就用构造函数别偷懒。后期你熟练了用malloc的时候也得记得memset一下。3. 链表的基本操作遍历、插入、删除的完整实现3.1 遍历链表的底层能力走地图遍历是所有链表操作的基础。一个链表在内存里是分散的你只能通过next指针一个一个跳过去。遍历的思路特别简单用一个临时指针指向head然后循环里输出数据再把指针指向next。直到指针变为nullptr说明走到链表尾部了。void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { std::cout cur-val - ; cur cur-next; } std::cout nullptr std::endl; }这段代码里的核心一句就是cur cur-next;。你千万不要写成cur链表在内存里不是连续的cur不会走到下一个节点只会把一个随机地址当成下一个节点然后就崩了。我遇到过不少初学者在遍历链表时习惯用while(cur)判断我个人更喜欢while (cur ! nullptr)虽然效果完全一样但可读性更强新手能明确地看到我们处理的边界条件是什么。3.2 在头部插入节点最快的一个操作头部插入是所有插入操作里最简单的因为你不需要找什么位置直接在head前面塞一个新节点即可。ListNode* insertAtHead(ListNode* head, int val) { ListNode* newNode new ListNode(val); newNode-next head; // 新节点指向原来的头节点 return newNode; // 新节点成为新的头节点 }注意这里有个关键点我们是用返回值把新的头节点传出来的。很多初学者会这么写void insertAtHead(ListNode* head, int val) { ListNode* newNode new ListNode(val); newNode-next head; head newNode; // 想当然地以为改了head }然后发现链表根本没变。原因就是head这个指针是按值传入函数的函数内部修改的是形参的副本。要真正改原指针要么用二级指针ListNode** head要么就通过返回值传递。新手阶段我建议直接用返回值的方式最直白也最不容易出错。3.3 在中间位置插入节点先找到位置再接线假设我要在第index个数据节点之前插入一个新节点。核心逻辑分两步先遍历找到第index-1个节点也就是前驱节点然后把新节点接到它后面。很多人第一次接触会以为插入要修改很多指针其实单链表的节点插入只需要改两行核心代码ListNode* insertAtIndex(ListNode* head, int val, int index) { if (index 0) { return insertAtHead(head, val); } ListNode* dummy new ListNode(0); // 这里其实引入头节点最方便 dummy-next head; ListNode* cur dummy; // 找到第index个位置的前一个节点 for (int i 0; i index cur-next ! nullptr; i) { cur cur-next; } ListNode* newNode new ListNode(val); newNode-next cur-next; // 新节点先指向原来的下一个节点 cur-next newNode; // 前驱节点再指向新节点 return dummy-next; }这里有个顺序问题是新手最容易犯的两行赋值语句的顺序。一定是先让新节点指向下一个节点再改前驱的指向。如果反着来cur-next newNode; newNode-next cur-next; // 这时候cur-next已经变成newNode自己了这样新节点就指向了自己剩下的链表直接断掉了。所以对于单链表的插入我习惯用一句口诀记忆先连后继再改前驱。这个顺序千万不能搞错。3.4 删除节点如何优雅地跳过目标节点删除节点在逻辑上是插入的反向操作。目标是让目标节点的前驱节点直接指向目标节点的后继节点然后释放目标节点的内存。ListNode* deleteNode(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* target cur-next; cur-next cur-next-next; // 跳过目标节点 delete target; // 释放内存 break; } cur cur-next; } return dummy-next; }删除的时候有一个大坑判断条件藏得很深。我们的遍历实际上是在检查下一个节点是不是要删的节点而不是看当前节点。为什么这么做因为单链表只有后继指针没有前驱指针。你走到当前节点的时候你是无法回头去改上一个节点的指向的。所以标准的删除操作永远是把前驱锁在cur上然后审视cur-next。这其实就是为什么dummy节点在删除操作里特别重要的原因当你要删除的正好是首元素时虚拟头节点能让逻辑完全统一。另外删除操作之后别忘了delete释放内存。如果你用的是new申请的节点不delete就会内存泄漏。C和Python不一样没那么多自动管理内存的机制。4. 进阶操作精讲反转链表、合并有序链表和快慢指针4.1 反转链表指针方向的全面倒转这个题基本上是所有面试、考试里链表部分的必考题也是检验你有没有真正理解指针操作的关键题。反转的核心思路非常朴素遍历过程中把每个节点的next指向它的前一个节点。但因为每个节点只能往前走不能往后走所以你必须提前保存好前驱节点和原后继节点ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nextNode cur-next; // 先保存原后继 cur-next prev; // 反转指针方向 prev cur; // 前驱前移 cur nextNode; // 当前节点前移 } return prev; // 最后prev就是原链表最后一个节点也就是新链表的头 }我第一次写这段代码的时候总觉得prev和cur的移动顺序很容易乱。后来我总结了一个辅助记忆方式nextNode是临时仓库cur-next是改方向prev和cur是同步后移。只要画一次图把prev、cur、nextNode三个指针的位置标出来整个过程就一目了然了。还有一个很有意思的点反转后的头节点是原来的尾节点。所以函数结尾返回的是prevcur在退出循环时已经变成了nullptr是不能再当返回值用的。4.2 合并两个有序链表谁的节点小谁就先进新链表合并两个有序的单链表这道题在考试和热搜词里都是高频词。要求是给你两个升序链表合并成一个新的升序链表。解题思路像是在排队时比较两个人的身高矮的先走一步然后继续比下一轮。这是比较典型的双指针遍历思路ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } // 处理剩余节点 if (l1 ! nullptr) tail-next l1; if (l2 ! nullptr) tail-next l2; return dummy-next; }这个实现有个小细节值得注意我没有新建节点而是直接复用了原来两个链表里的节点。节点还是那些节点只是重新排列了它们之间的指向。所以这个操作的空间复杂度是O(1)只额外用了一个dummy节点。代码最后的两个if判断是为了把没有比完的剩余链表直接接上去。因为两个链表都是有序的剩下的节点一定都是当前最大的那一段所以直接拼接即可不需要再逐一遍历了。很多初学的人在这里会写一个循环其实没必要效率反而低了。4.3 快慢指针链表的双人跑步技巧如果说反转链表和合并有序链表是算法题常客那么快慢指针就是解决链表追及问题的一把钥匙。最经典的场景有两个查找链表的中间节点以及判断链表是否有环。找中间节点的做法是快指针每次走两步慢指针每次走一步。当快指针到达链表末尾时慢指针刚好走到中间。原理和两个人跑步一样速度差一倍相同时间内路程正好差一倍。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; }判断链表是否有环的思路是如果快慢指针在环里经过若干次循环后相遇了就说明链表有环。就像两个人在环形跑道上跑步速度不一样跑的时间足够长的话快的人一定会追上慢的人。快慢指针的细节在于while条件的顺序。我强烈建议你写字时先写fast ! nullptr再写fast-next ! nullptr防止代码先判断fast-next结果fast已经为空了直接访问空指针的next导致崩溃。这种错误在LeetCode上跑的时候会显示member access within null pointer of type struct ListNode。4.4 循环链表和其他变体单向链表之外还有循环链表和双向链表。循环链表就是把最后一个节点的next重新指向头节点形成一个环。它的好处是你从任何一个节点出发都能遍历到所有节点比较适合环形队列、操作系统进程调度等场景。双向链表则是每个节点多一个prev指针指向前驱节点。优点是删除、插入的时候不需要再找前驱了代价是每个节点会多占用8字节的指针内存。C标准库里的std::list就是一个双向链表容器如果你不想自己造轮子可以直接用它。我在实际开发里遇到过需要快速删除任意节点、又需要双向遍历的需求最终选择的就是手写双向链表。操作虽然比单链表复杂一点点但逻辑思路是完全相通的核心就是先处理后继再处理前驱最后把边界条件补齐。5. C里链表的另一面使用STL和常见踩坑清单5.1 别急着造轮子std::list了解一下手写链表虽然学习意义很大但在真正的工程开发里标准库已经提供了非常成熟的链表容器std::list。它实现的是双向链表提供了push_back、push_front、insert、erase、remove等常用接口。用起来非常直观#include list std::listint myList; myList.push_back(1); myList.push_front(0); myList.insert(next(myList.begin()), 99); // 在第二个位置插入99 myList.remove(0); // 删除值为0的节点需要提醒的是std::list的排序不能用算法库里的std::sort因为std::sort要求随机访问迭代器而链表迭代器不满足。这是C标准库里一个出了名的坑。你要用myList.sort()这个成员函数它内部针对链表做了特殊优化。高频场景下如果你需要频繁在头部插入并保持顺序std::list和手写单链表效率是差不多的。但如果数据量不大、操作不频繁我个人反而更推荐直接用std::vector因为vector在内存里连续存储缓存命中率高在很多实际场景里跑得反而比链表的散落内存快得多。5.2 较常遇到的问题汇总根据我自己的经验和搜索热词来看学链表时大家翻车的地方其实非常集中总结出来也就这么几个你可以用来自查常见问题原因分析预防方案没初始化next指针指针未置空指向垃圾地址写构造函数或new完立刻初始化新建节点忘了delete内存泄漏删除操作后显式delete或使用智能指针把head指针直接传入函数函数内修改的是形参原链表没变使用返回值或二级指针插入顺序写反先改前驱next导致链表断链记住先连后继再改前驱循环条件越界空指针访问遍历时加cur ! nullptr判断如果你在写链表过程中遇到了段错误别急着看答案先用纸笔画一下当前链表的指向。指针问题用肉眼debug困难画图是最有效的方式。这是我在实际带新人时发现的一个很实用的技巧不少人卡了一个下午的问题一画图就立刻明白了。5.3 给新手的练习建议链表这个知识点只看不写是永远学不会的。我建议你按下面这个顺序练手每一个都自己敲一遍不要复制粘贴实现一个带头节点的单链表支持尾部插入、头部插入、遍历输出。实现删除指定值的操作注意边界条件空链表、只有一个节点、删除的是头节点。实现反转链表画图辅助理解三个指针的移动过程。实现合并两个有序链表。尝试用快慢指针判断链表是否有环再创建一个带环链表测试你的代码。等这5个都能不看答案独立写出并跑通你对链表的理解就已经超过绝大多数初学C的人了。我个人教了这么多轮C下来最大的体会是链表是整个数据结构学习的分水岭。数组时期你只需要理解下标而到了链表你真正开始接触引用地址内存管理这一套底层逻辑了。学的时候别急卡住了就画图把一个节点的前后关系画清楚了后面的反转、合并、快慢指针都会一路通畅。