算法学习到第五天终于轮到链表了。说实话我在前四天连续啃数组、栈、队列这些线性结构的时候心里一直有个坎——数组用起来明明那么顺手为什么还要单独搞一个链表出来但今天花了一整天从结构体定义到各种操作再到刷了几道经典题算是彻底明白了链表的本质就是用“关系”取代“位置”这也是它能在任意位置高效插入删除的根本原因。这篇就当是我个人链表学习的阶段总结也分享给同样在数据结构路上挣扎的朋友。我会把今天踩过的坑、想通的点、以及那些“人话版”的理解全部写出来尽量做到即使你是零基础也能跟着思路一步步把链表啃下来。1. 链表到底是什么为什么算法学习绕不开它1.1 像火车车厢一样的内存结构我第一次听“链表”这个词脑子里没有任何画面感。后来看到一个比喻一下就通了链表就是一列火车每节车厢里装着一个数据同时还写着“下一节车厢在哪里”。你要找到第五节车厢没法直接跳过去必须从车头一节一节往后找。这是它和数组最本质的区别。从这个角度看链表里的每个“车厢”在专业术语里叫节点它内部由两部分组成数据域真正存储的数据可以是一个整数、一个字符也可以是一个结构体对象。指针域存着下一个节点或者上一个节点的地址。单链表里每个节点只知道自己后面是谁双链表则会记录前后两个邻居循环链表则是把最后一个节点的指针重新指向头节点形成闭环。这几种变体在今天学习过程中我全都接触了一遍但其实核心思想就一句话用指针把散落在内存各处的节点串起来。内存分配上链表节点不像数组那样要求一整块连续空间。你可以今天 new 一个节点在地址 0x0012明天 new 一个节点在地址 0xFFE2它们互不相邻也完全没关系只要前一个节点记住后一个节点的地址整条链就是完整的。这种灵活性在频繁插入删除的场景里价值非常大。1.2 数组和链表一个管索引一个管关系要理解链表的价值必须把数组和链表放一起对比。我在学习过程中整理了一张对比表这对我理解“什么时候用数组、什么时候用链表”帮助特别大操作维度数组链表内存空间需要连续内存可以是离散内存分散存储按下标访问O(1)直接算出地址O(n)必须从头遍历插入/删除O(n)要搬动后续所有元素O(1)只需修改指针指向前提是已知目标位置空间占用相对紧凑只有数据每个节点要额外存指针有开销扩容需要重新分配整块更大的空间随时 new 一个节点接上去就行从表里能看出数组强在“访问”链表强在“修改”。如果一段程序的核心操作是频繁按下标查数据比如搜索引擎的倒排索引用数组更合适如果核心操作是不断往中间插数据、删数据比如缓存淘汰机制里的 LRU 链表那链表的优势就体现出来了。所以算法学习里老是强调链表不是因为它比数组高级而是因为它让你多了一把解决问题的工具。有的场景用数组难受得很换成链表几行代码就清爽了。这个体会在我后面写缓冲区管理、任务队列时特别深。2. C语言结构体链表从0到1手写一个单链表2.1 结构体定义和创建节点的细节学链表最扎实的方式是先用 C 语言手写一遍。C 语言的指针概念和链表天然契合很多教你“用 python 写链表”的教程实际上把内存和指针的细节全都藏起来了初学者容易看得懂但没抓住本质。C 语言定义单链表节点是这样#include stdio.h #include stdlib.h typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node;很多初学者看到struct Node *next会懵结构体里面怎么还能包含一个自己类型的指针这里要理清不是包含一个节点对象而是包含一个“节点地址”。就好比每节车厢里放的不是另一节车厢而是一张写着“下一节车厢位置”的字条。创建新节点时用malloc在堆上分配内存// 创建一个值为 val 的新节点返回指向它的指针 Node* createNode(int val) { Node* newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; }malloc之后一定要检查返回值是否为 NULL。这一步虽然简单但是很多程序崩溃都源于此。如果分配失败还直接去操作newNode-data就是典型的空指针访问程序直接段错误。我建议所有使用malloc的地方都加上判空这是 C 语言程序员的基本素养。2.2 头结点、头指针和内存释放链表里有两个概念特别容易混淆头指针和头结点。头指针指向链表第一个节点的指针。它就像火车的车头只要握住它整条链都能遍历到。头结点在真正的第一个节点前额外增加的一个节点数据域不存业务数据只作为统一操作的哨兵。加了头结点的好处是不管链表是不是空头指针始终指向一个存在的节点插入删除的代码可以少写很多 if 特判。我第一次写插入时没带头结点空链表插入要单独写逻辑非空插入又写一遍代码又臭又长。后来加上头结点所有插入只要你从head往后遍历到目标位置统一用同一套逻辑清爽多了。关于内存释放C 语言没有垃圾回收每个malloc出来的节点最后都要手动free。我写了一个销毁整个链表的函数void destroyList(Node* head) { Node* cur head; Node* tmp; while (cur ! NULL) { tmp cur-next; // 先保存下一个节点地址 free(cur); // 释放当前节点 cur tmp; // 移动到下一个节点 } }这里有个极容易踩的坑free(cur)之后再访问cur-next是未定义行为因为这块内存已经交还给系统了。所以必须先tmp cur-next保存下一个节点地址再 free 当前节点。这个“先保存后释放”的顺序我在今天练习中至少写错了三次每次都是程序跑着跑着突然崩掉。如果你用 C可以采用 RAII 思想封装一个链表类析构函数里负责释放所有节点这样能避免忘掉释放的问题。不过学习阶段我更建议先用 C 手动管理一遍内存才能真正体会链表底层的“血肉”。3. 这三种操作必须刻进脑子里遍历、插入、删除3.1 从头部到尾部链表的遍历思路链表的遍历逻辑是所有操作的地基。它的核心就是一个循环从第一个节点开始顺着next指针依次走直到某个节点的next为 NULL说明到末尾了。// 打印链表中所有节点的值 void printList(Node* head) { Node* cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }这里最需要注意的是千万不要在循环里移动 head 指针本身。我一开始图省事直接while (head ! NULL) { ... head head-next; }打印完整个链表之后head已经指向 NULL 了。等下一次再用这个链表时发现所有节点都“丢”了连头都找不回来。正确做法是定义一个临时变量cur让它去遍历head作为链表的入口永远不动。回过神来想想这跟“你手里的地址能让你重新找到家”一个道理——链表头就是那个家的地址你用临时指针出门逛街怎么逛都可以但家的地址不能丢。遍历也承载了很多衍生操作比如求链表长度、查找某个值是否存在、统计链表最大值等等。你会发现一旦理解了“从头走到尾”这个框架后面这些题目基本是加一些 if 判断就完事。3.2 头插法和尾插法插入节点的两种基本功插入操作本质上就是把一个新节点接到链表的两个已有节点之间。最经典的是头插法和尾插法我分别来说。头插法把新节点插入到头结点和第一个数据节点之间。注意我说的是带头结点的场景。void insertAtHead(Node* head, int val) { Node* newNode createNode(val); newNode-next head-next; // 新节点先指向原来的第一个数据节点 head-next newNode; // 头结点再指向新节点 }这里有个顺序问题特别关键必须先把新节点的 next 指向原第一个节点再把 head 的 next 改为新节点。如果你把两行写反了head-next先变成了newNode那原来的第一个节点地址就找不到了后面的链会全部丢失。这个错误初学者基本都会犯至少一次代价就是整个链表惨遭截断。尾插法把新节点接到链表末尾。void insertAtTail(Node* head, int val) { Node* newNode createNode(val); Node* cur head; while (cur-next ! NULL) { cur cur-next; // 一直走到最后一个节点 } cur-next newNode; // 让原尾节点的 next 指向新节点 }尾插法的时间复杂度是 O(n)因为必须从头走到尾。如果你经常在尾部插入可以额外维护一个tail指针每次插入完更新它这样尾插就变成 O(1) 了。这个优化思想在 LRU 缓存这种频繁头尾操作的场景中非常重要。头插法和尾插法合起来看你会发现一个重要规律插入操作中指针修改的顺序永远是“先把新节点接到后面的节点上再让前面的节点指向新节点”。就像你插队先和新队伍里的人搞好关系再让你前面的人松手。3.3 删除节点最容易踩的坑断链和内存释放删除节点的核心逻辑是找到目标节点的前一个节点让它跳过目标节点直接指向目标节点的下一个节点。void deleteNode(Node* head, int val) { Node* cur head; // cur-next 是我们要判断的节点 while (cur-next ! NULL) { if (cur-next-data val) { Node* tmp cur-next; // 保存待删除节点 cur-next tmp-next; // 跳过它直接指向下一个 free(tmp); // 释放内存 return; } cur cur-next; } printf(没有找到值为 %d 的节点\n, val); }这里犯了错就会出大问题有人删除节点后没有free导致内存泄漏程序跑久了内存越占越多有人在free之后还去读tmp-data导致随机值或者崩溃。删除断链释放两步都不能少。这和饭吃完要洗碗是一个道理不洗碗不释放内存厨房堆内存很快就没有干净碗用了。特别提醒free在 C 里对应的是delete如果节点是用new创建的释放就必须用delete。混用malloc/free和new/delete在遇到复杂对象时可能引发灾难比如构造函数析构函数不匹配、内存泄漏甚至段错误。这里我再补充一个双链表的删除场景。双链表删除时多了一个prev指针写起来是这样的// 假设 node 指向待删除节点 node-prev-next node-next; node-next-prev node-prev; free(node);双链表的优势在于你知道某个节点的地址后不需要追溯前驱就能完成删除时间复杂度 O(1)。这也是为什么在需要频繁删除指定节点的场景比如操作系统内核的进程管理、浏览器的前进后退历史双链表会是更合适的选择。4. 链表不是孤岛栈、队列、循环链表的实际应用场景4.1 用链表实现栈和队列对应关系分析栈和队列是两种更抽象的逻辑结构它们的底层既可以用数组实现也可以用链表实现。我在学完链表之后回头再看栈和队列一下就看明白了。栈的核心是先进后出LIFO所有操作只发生在栈顶。用链表实现栈特别顺把链表的头部当成栈顶入栈就是头插法出栈就是删除第一个节点。代码简洁而且不用担心栈满的问题前提是内存够因为节点都是动态分配的。队列的核心是先进先出FIFO入队发生在队尾出队发生在队头。用单链表实现队列需要维护两个指针head指向队头tail指向队尾。入队操作是尾插法出队操作是删除头节点。如果单独维护 tail入队的复杂度就从 O(n) 降到了 O(1)。我在学习的时候特别喜欢把这几者放在一起对比因为它们之间不是割裂的而是一层层的抽象关系数据结构实现方式特点典型应用顺序栈数组访问快、容量固定函数调用栈、表达式求值链栈链表动态扩容、不怕满浏览器后退、撤销操作顺序队列数组会有假溢出需要环形数组消息队列、任务调度链式队列链表长度动态灵活打印任务排队、网络请求排队4.2 循环链表和约瑟夫问题循环链表是单链表的一个变种最大的区别就是最后一个节点的 next 不再指向 NULL而是重新指向头结点整个链表形成一个环。因此从任意一个节点出发都能遍历到所有其他节点。约瑟夫环问题就是循环链表最经典的落地场景。问题描述是n 个人围成一圈从第 k 个人开始报数报到 m 的人出列然后从下一个人继续报数直到所有人都出列求最后的幸存者。用循环链表实现这个逻辑非常直观Node* josephus(int n, int k, int m) { // 1. 构建循环链表 Node* head createNode(1); Node* cur head; for (int i 2; i n; i) { cur-next createNode(i); cur cur-next; } cur-next head; // 连成环 // 2. 从第 k 个节点开始数 Node* prev cur; // prev 是 head 的前一个节点 Node* p head; for (int i 1; i k; i) { prev p; p p-next; } // 3. 不断淘汰数到 m 的人 while (p-next ! p) { // 只剩一个节点时结束 for (int i 1; i m; i) { prev p; p p-next; } printf(出列: %d\n, p-data); prev-next p-next; free(p); p prev-next; } return p; // 最后剩下的节点 }这个代码我第一次看觉得绕后来自己动手画图才明白prev始终指向当前位置的前一个节点因为删除当前节点之后必须知道它前面是谁才能继续往下走。循环链表的核心操作场景里维护“前驱”比维护“当前”更重要。这个过程也让我理解了一个通用规律处理链表的环形场景本质上是把“线性走走不动了”变成“永远走不完”非常适合用来模拟循环轮转的逻辑比如操作系统的进程调度、时间片轮转算法底层都用到了类似的环形队列思想。4.3 链表在真实系统里的影子很多人学链表会问一句这玩意儿除了考试还有什么用其实真实系统里链表无处不在只不过被封装在库或者框架内部你不一定直接感觉得到。比如操作系统的内存管理中空闲内存块的维护通常用空闲链表文件系统的目录结构、块分配表也会用到链表浏览器的前进、后退功能核心就是一个双链表每个页面节点同时保留“下一页”的指针和“上一页”的指针Cache 的 LRU 淘汰策略里最经典的实现就是“哈希表 双向链表”哈希表负责 O(1) 查找双向链表负责 O(1) 插入删除Java 的LinkedList、Python 的collections.deque底层都是有相应链表结构的影子。我当初学完链表之后再去看这些框架源码发现自己能轻松想象出内存中的节点关系图了。这正是学习数据结构的价值——不是让你徒手写轮子而是让你具备看懂底层、设计方案的底气。5. 面试常考的经典题目一题一题拆给你看5.1 反转链表三个指针就能搞定反转链表是面试出镜率最高的链表题我和它整整纠缠了一个下午。它的要求很简单输入 1 - 2 - 3 - 4 - NULL输出 4 - 3 - 2 - 1 - NULL。迭代法是我认为最好理解的版本核心是三个指针prev前一个、cur当前、nextTemp下一个。Node* reverseList(Node* head) { Node* prev NULL; Node* cur head; while (cur ! NULL) { Node* nextTemp cur-next; // 先记录下一个节点 cur-next prev; // 当前节点指向前一个 prev cur; // 前一个指针后移 cur nextTemp; // 当前指针后移 } return prev; // cur 为 NULL 时prev 就是新链表的头 }这段代码的灵魂在循环内部那四行思路是把每一个节点的 next 指针从指向“后面”变成指向“前面”。每一步中nextTemp负责保存还没处理的部分防止断链后找不回来。这就好比整理一列反向排列的抽屉你每次只动一个抽屉但必须先把旁边的抽屉位置记住。我一开始看这段代码总觉得绕后来在纸上手动画了一遍 1-2-3 的完整过程才真正看明白。这里强烈建议大家反转链表这种题光在脑子里推是推不明白的一定要在纸上画出每一步三个指针的位置变化。第一次画可能花半小时但画完就彻底通了。递归版本也值得一看Node* reverseListRecursive(Node* head) { if (head NULL || head-next NULL) { return head; } Node* newHead reverseListRecursive(head-next); head-next-next head; // 让下一个节点指回当前节点 head-next NULL; // 断开当前节点原来的指向 return newHead; }递归版本第一眼不好理解但它的逻辑其实很优美假设你已经把head后面的整条链都反转好了现在只需要把head挂到这条新链的末尾。也就是“先信任递归能处理好剩下的事再来解决当前节点”。递归学到最后你会发现许多链表、树的问题都可以用这种“相信子问题”的思维来简化。5.2 快慢指针找环和找中间节点共用一张解题卡快慢指针是链表题里的一种双指针技巧核心是让两个指针同时出发一个一次走一步另一个一次走两步。判断链表是否有环这是面试中很常见的一道题int hasCycle(Node* head) { Node* slow head; Node* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; // 慢指针走一步 fast fast-next-next; // 快指针走两步 if (slow fast) { return 1; // 相遇说明有环 } } return 0; // 快指针走到头说明无环 }这个思路就像两个人在环形跑道上跑步一个快一个慢如果跑道是环形的快的人总会追上慢的人如果跑道是直线快的人就会先跑到终点。如果不理解为什么快指针一定能追上慢指针可以想一想每一次移动快指针相对慢指针多走一步那么在环形结构里它俩的距离必然会不断缩短直到相遇。找链表的中间节点也用同一套思路快指针到末尾时慢指针刚好走到中间。Node* findMiddle(Node* head) { Node* slow head; Node* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }用偶数长度链表测试一下你会发现慢指针指向的是中间两个节点中靠右的那一个。有些问题里需要靠左的中间节点就要在循环条件上做微调。这种“控制边界条件来影响最终结果”的细节正是刷题时需要慢慢积累的手感。快慢指针这两个场景结合起来看其实都遵循同一个底层原理利用两个指针速度差把一维线性遍历变成“相对位置控制”。一旦掌握这个思维很多看起来毫无头绪的链表题都会变得有迹可循。5.3 合并两个升序链表归并排序的入门钥匙题目模型是已知两个单链表分别按升序排列要求合并成一个新的升序链表。这其实和归并排序中的 merge 过程一模一样。Node* mergeTwoLists(Node* l1, Node* l2) { Node dummy; // 栈上创建哑结点不需要 malloc 和 free dummy.next NULL; Node* tail dummy; // tail 始终指向新链表的末尾 while (l1 ! NULL l2 ! NULL) { if (l1-data l2-data) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } // 哪条链还有剩余直接接上 tail-next (l1 ! NULL) ? l1 : l2; return dummy.next; }这段代码值得称道的细节是哑结点dummy node技巧。使用哑结点后你不需要单独处理“合并后的第一个节点是谁”这种特判新链永远有一个确定的头最后返回dummy.next即可。我第一次写这题时没加哑结点代码越写越长各种边界条件堆成一团后来加了哑结点代码逻辑瞬间清晰。合并两个升序链表的思路实际上就是归并排序最核心的一步把两个已经有序的序列通过不断取较小值合并成一个有序序列。掌握了这个函数之后学归并排序、多路归并都能从这里延伸出去。另一个常见的变体是“已知两个长度为 m 和 n 的升序单链表求合并后的第 k 个元素”。这种题在工程上也很常见比如搜索结果的合并、日志文件的多路归并。核心思路依然是双指针比较只是在计数到 k 时停下来返回即可。6. 实战复盘这几天踩过的链表大坑6.1 崩溃型 Bug空指针、野指针、内存泄漏链表编程中遇到的 Bug大多数可以归纳成三类空指针访问、野指针、内存泄漏。空指针访问在使用一个指针之前没有判断是否为 NULL然后去访问它的成员程序直接段错误。我遇到最多的情况是malloc失败后没检查或者是链表本身就是空的我却一上来就head-next。野指针一个指针指向的内存已经被释放但指针变量还保留着旧地址。释放后没有把指针置为 NULL后续又去访问这是最隐蔽、最让人抓狂的 Bug因为错误发生的时刻可能离真正原因隔得很远。内存泄漏用malloc分配了内存却一直不free。程序短跑没问题跑久了内存占用持续上涨最终系统被拖垮。我在写代码的时候逐渐养成了几个习惯不管什么指针使用前先检查再动手释放后立刻把指针置为 NULL写循环分配节点的代码时心里一定要有对应的“回收”方案。另外Linux 下我用 valgrind 跑内存检测Mac 下我用 AddressSanitizer在编译参数里加-fsanitizeaddress这些工具能直接告诉你哪一行内存访问出错、哪里泄漏了排查效率翻倍。常见崩溃类型典型原因一句话避坑段错误访问了 NULL 指针或已释放内存使用前判空释放后置空程序卡死链表成环导致 while 循环停不下来用快慢指针检测循环多用边界条件测试数据丢失插入删除时指针顺序写反记住“先连新再断旧”内存泄漏malloc 后没有 free每次 malloc 都要有对应 free 的觉知6.2 断链顺序插入删除操作的经典翻车现场链表的插入删除最核心的就是指针修改顺序。我在学习过程中反复犯同一个错误最后总结出一个容易记忆的口诀先接新再断旧。以“在节点 p 后面插入新节点 s”为例正确顺序是s-next p-next; // 新节点先接上原来的后继 p-next s; // 再让 p 指向新节点如果顺序颠倒p-next已经被覆盖成 s原来后继节点的地址就找不到了后半条链直接丢失。删除节点时也有类似问题先把要删除的节点从链上摘下来再做 free。很多新手是在 free 之后还试图去访问它的 next这同样是未定义行为。我个人的体验是这类问题没办法只靠背口诀解决一定得动手画图。每写一个插入或删除函数先在草稿纸上画出链表的节点和箭头然后用铅笔把“改哪条箭头、画哪条新箭头”标出来。等你画的次数多了代码里指针顺序自然就形成肌肉记忆。6.3 我的学习方法纸上画图、写测试用例、做总结最后想分享三个我个人觉得非常有效的学习方法。第一个是纸上画图。这不是客套话是我这几天最深刻的体会。链表的核心就是指针的指向变化而指针的变化用文字很难讲清楚用图却一目了然。我现在遇到任何链表算法题第一件事不是敲代码而是先在草稿纸上画出链表结构然后用箭头模拟每一步操作。这个方法至少帮我省了大半天纠结时间。第二个是写足测试用例。很多人写完函数就测一个 happy path结果一到边界条件就崩。链表这块特别要测空链表、只有一个节点的链表、删除头节点、删除尾节点、插入到头部、插入到尾部、链表中没有目标值等等。我建议每次都把这些用例全部过一遍哪怕代码多几行也能杜绝绝大多数隐藏问题。第三个是画思维导图或者写总结。我会在每天学习结束后用十分钟把当天学到的所有知识点、踩过的坑、写过的代码整理成笔记。这个动作看起来简单但效果拔群。因为写总结的过程就是你强迫自己把“好像懂了”变成“真的懂了”的过程。今天这篇关于链表的文章某种意义上就是我这个习惯的产物。链表的学习不是一个“看一遍就会”的东西但只要你能静下心把结构体定义、遍历、插入、删除这四板斧练熟再配上几道经典题目后面的双链表、循环链表、跳跃表都会轻松很多。我个人的经验是链表的难点从来不是语法而是那个“指针到底指向哪里”的脑内建模而建模能力只能靠动手画图和写代码来练。希望这篇学习笔记能帮到正在啃链表这块硬骨头的你。学习算法的路上我们都在同一条链表上一站一站地前进。