写链表题你会不会也有这种感觉看别人的代码好像全懂自己一动手就崩要么空指针要么死循环要么忘了释放内存。尤其是单链表它不像数组那样有下标所有操作都得靠指针一步一步走初学者很容易绕进去。这篇文章我打算从“它到底解决了什么问题”讲起把节点、插入、删除、反转、快慢指针、虚拟头节点这些全部过一次再给一份可以直接跑的C语言实现最后聊聊那些刷题和写工程代码时一定会踩的坑。不管你是刚学数据结构还是在准备算法面试又或者只是需要快速捡起链表知识这篇都适用。1. 先搞清楚单链表到底解决什么问题1.1 数组的痛点和链表的出现数组在内存里是一段连续空间下标访问非常快比如arr[3]直接就是“首地址 3 * 元素大小”一步到位。但连续空间也带来了两个麻烦第一插入一个元素到中间后面的元素全部要往后挪删除一个元素后面的元素全部要往前挪最坏情况是 O(n)。第二数组扩容很僵硬你开了一个固定大小装满了就得申请更大的空间再整体拷贝。单链表就是来对付这两个问题的。它的核心思路很简单让每个元素单独存放不要求连续每个元素里带一个“指向下一个元素的指针”像一串珠子用绳子串起来一样。你想在中间插入一个节点只要把前一个节点的指针指向新节点新节点的指针指向后一个节点就行剩下的节点完全不用动。这个操作的时间复杂度是 O(1)前提是你能快速找到插入位置。我有一个不太严谨但很好记的类比数组就像电影院里一排固定座位每个人必须坐在指定位置有人离开座位大家得整体挪屁股单链表就像小朋友手拉手排队你想在中间塞个人只需要让他拉住前面人的手再让后面的人拉住他的手整条队伍不用散。这个类比虽然不完全严谨但对理解“链表操作为什么不用搬迁数据”非常有帮助。1.2 单链表的最小构成单元节点单链表的基本单位叫“节点”每个节点只有两部分数据域和指针域。数据域存你想存的值指针域存“下一个节点在哪里”。在 C 语言里节点一般用一个结构体定义typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node;这里有个初学者最容易懵的点结构体里为什么能用struct Node *next指向自己这听起来像“一个人手里牵着另一个人的手而那个人也长着同样的结构”但这是合法的。指针存的是地址结构体定义的时候只需要知道“有一个指向同类型结构体的指针”不需要先把这个结构体完整地用完。换句话说我们先说“每个节点里有个箭头指向下一个同类型的节点”这个描述本身是自洽的。如果你更熟悉 Python可以想象成class Node: def __init__(self, data): self.data data self.next None在 Python 里self.next可以直接指向另一个Node对象因为 Python 是动态语言对象引用不需要预先确定类型。本质上和 C 语言的指针是一个意思只是 C 里说得更直白地址。1.3 头指针、尾节点与“链表为空”的判定整个链表靠一个“头指针”进入头指针指向第一个节点。第一个节点没有前驱最后一个节点的 next 是空指针也就是NULL英文里也叫None或null意思是“后面没人了”。所以判断一条单链表是不是空链表只要看头指针是不是NULLNode *head NULL; // 空链表 if (head NULL) { // 链表为空 }为什么这里特别要强调空指针因为后面所有操作的边界判断几乎都围绕它展开。你要遍历链表循环条件是while (p ! NULL)你要删除节点就得保证p-next不会访问到空指针的成员你要在尾部插入也得先判断链表是不是空。指针这个东西一旦让它指向了空地址还继续访问成员程序轻则崩溃重则产生你根本查不出来的诡异 bug。这里顺带引入一个后面高频出现的概念虚拟头节点也叫哨兵节点、dummy head。它是一个不存业务数据的节点head 永远指向它真正的数据从这个节点的 next 开始。这样做的好处是空链表和非空链表在代码里不再需要分别考虑插入、删除的第一个节点都可以当作“普通节点”来处理。后面讲操作时你会看到它有多香。2. 核心操作的完整推演插入、删除、查找2.1 从头到尾走一遍遍历与查找单链表没有下标任何操作都得从头指针开始沿着 next 一个一个往下走。遍历一个链表最标准的写法长这样void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }你注意看这个循环的推进方式p p-next。这一句是链表的灵魂。每次循环访问完当前节点就把指针拨到下一个节点。“走一步看一步”就是单链表的节奏。查找某个值是否存在也一样必须从头找到尾平均要比较 n/2 次最坏情况是 n 次所以查找的时间复杂度是 O(n)。数组的随机访问是 O(1)这是链表比不过数组的地方后面我会专门一节讲“谁更快”不能只看时间复杂度。2.2 插入的两种姿势头插法和尾插法插入操作是理解链表指针修改的绝佳例子。先说“头插法”也就是把新节点插到链表最前面。步骤只有两步Node *insertHead(Node *head, int val) { Node *newNode createNode(val); newNode-next head; // 新节点指向原来的第一个节点 head newNode; // 头指针指向新节点 return head; }这里有个顺序问题一定先修newNode-next再改head。如果反过来先把head指向了newNode那原来的链表就丢了你再也找不到原来第一个节点的位置。很多初学者的野指针问题都是这么来的。再说“尾插法”就是在链表末尾追加节点。由于单链表只有 next 没有 prev你没法直接知道“最后一个节点是谁”只能从头遍历到结尾Node *insertTail(Node *head, int val) { Node *newNode createNode(val); if (head NULL) { return newNode; // 空链表新节点就是头 } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; }注意这里的遍历条件是p-next ! NULL而不是p ! NULL。为什么如果写成while (p ! NULL)循环结束时 p 已经变成 NULL你根本不知道它的前驱是谁就没法把新节点接上去。你要找的是“最后一个有效节点”它的特征是 next 是空。这个条件我见过太多人写错了包括我自己当年也是在这里卡了半天。如果要在指定位置比如第 k 个节点后面插入思路是“先找到第 k 个节点再把它后面的关系改掉”。关键还是找到前驱。为什么是前驱因为你要修改的是前驱节点的 next 让它指向新节点而不是修改目标节点自己。2.3 删除操作的关键找到前驱节点删除一个节点比插入更考验逻辑。假设你想删除值为 val 的那个节点难点在于单链表只能顺着 next 往前走你走到目标节点时手里握着的只有目标节点自己但你要改的是它前驱节点的 next。前驱在哪你得用一个额外的指针跟踪。经典的删除代码长这样Node *deleteNode(Node *head, int val) { if (head NULL) return NULL; if (head-data val) { Node *tmp head; head head-next; free(tmp); return head; } Node *prev head; Node *cur head-next; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; free(cur); } return head; }这个代码最核心的就是prev和cur两个指针一前一后同步走就像两个人排成一队后面的人永远知道前面的人是谁。一旦cur找到目标prev就是它的前驱直接让prev-next cur-next然后把cur释放掉。头节点的删除要单独处理因为头节点没有前驱。如果你不想为头节点单独写 if那就用到前面说的虚拟头节点。虚拟头节点让你可以统一地处理“删除第一个数据节点”和“删除中间节点”这两种情况因为它们都变成了“通过前驱删除后一个节点”的同一套操作。2.4 虚拟头节点的妙用用一个 dummy 节点做哨兵链表真正的内容从dummy-next开始。初始化时dummy-next NULL然后所有插入删除都不需要对“头节点”做特判。我们重写一下删除Node *deleteNodeWithDummy(Node *dummy, int val) { Node *prev dummy; Node *cur dummy-next; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; free(cur); } return dummy; }这段代码里prev一开始指向 dummycur指向第一个真正节点。如果第一个节点就是要删的prev就是 dummy照样执行prev-next cur-next完全没有特判。这就是虚拟头节点最大的价值让边界情况和普通情况走同一条代码路径少一个 if 就少一处出错的可能。我做算法题时几乎不用裸头指针凡是涉及删除、在头部插入的题目第一反应就是加一个 dummy。这个习惯非常值得养成它能让代码短一截也更好调试。3. 一份可直接跑的 C 语言实现从定义到调试3.1 完整代码节点定义与四大核心函数概念讲再多不如一份能跑的代码实在。下面这份代码我建议你从头敲一遍不要复制粘贴。自己敲的时候注意每个-和每个NULL这是建立手感最快的方式。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *n (Node *)malloc(sizeof(Node)); if (n NULL) { printf(内存分配失败\n); exit(1); } n-data val; n-next NULL; return n; } void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); } Node *insertHead(Node *head, int val) { Node *n createNode(val); n-next head; return n; } Node *insertTail(Node *head, int val) { Node *n createNode(val); if (head NULL) { return n; } Node *p head; while (p-next ! NULL) { p p-next; } p-next n; return head; } int length(Node *head) { int count 0; Node *p head; while (p ! NULL) { count; p p-next; } return count; } int main() { Node *head NULL; head insertHead(head, 3); head insertHead(head, 2); head insertTail(head, 4); head insertHead(head, 1); printList(head); // 1 - 2 - 3 - 4 - NULL printf(length %d\n, length(head)); return 0; }这个程序包含创建节点、头插、尾插、打印、求长度五个基本函数。运行结果应该是1 - 2 - 3 - 4 - NULL。你可能会好奇为什么insertHead和insertTail都返回Node *因为头指针可能在插入时发生变化我们必须把新头指针传出来。如果写成void insertHead(Node *head, int val)你以为改了 head实际上在函数内部修改的只是一个拷贝外面根本没有变。3.2 逐行拆解关键函数的设计意图createNode里有句malloc内存分配很多人会忽略检查返回值。malloc有可能失败尤其在一些内存受限的嵌入式场景里。虽然日常跑 demo 时很少遇到但养成“分配完先检查”的习惯能帮你避开一种很隐蔽的崩溃拿到了空指针还往里面写数据一写写到了地址 0 附近直接段错误。insertTail为什么要在head NULL时直接返回n因为空链表没有“尾节点”新节点既是尾也是头。这个分支如果不写后面p-next就是访问空指针成员程序在你第一次给空链表添加节点时当场炸掉。这也是链表代码里最经典的一类问题没有考虑空链表。我见过很多同学调这类 bug会花很长时间打日志但实际上只要在纸上画两个图一个空链表、一个单节点链表把所有操作走一遍错误基本都能自己找出来。画图这个习惯学链表的人越早养成越好。3.3 边界条件自查清单链表代码能不能一次跑通基本就看边界情况处理得全不全。我给自己列了一个清单每写完一个操作都对照查一遍场景应该检查什么空链表所有操作都不能访问空指针成员只有一个节点删除后链表应为空头指针要变 NULL删除头节点头指针要更新旧头要释放删除尾节点倒数第二个节点的 next 要置 NULL目标值不存在遍历完整个链表后不做任何修改插入到头部旧头指针不能丢新节点 next 要接旧头插入到尾部遍历条件要用p-next ! NULL链表只有一个节点时求长度结果应为 1循环要对这张表不只是用来应付作业的面试时写到链表题边界条件往往是考察重点。你写完代码后主动把这些场景在脑子里过一遍能直接看出很多 bug比跑测试更快。4. 进阶操作反转、环检测、有序合并4.1 反转链表的迭代法反转单链表是面试高频题也是检验你是否真的理解指针关系的试金石。迭代法的思路是用三个指针prev、cur、next从头开始一个一个把节点的 next 掉头。Node *reverse(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *next cur-next; // 先保存后一个节点 cur-next prev; // 把当前节点的 next 指向前面 prev cur; // 前指针前移 cur next; // 当前指针前移 } return prev; // 循环结束时 prev 就是新头 }为什么要先保存next因为一旦执行了cur-next prev当前节点原本指向后面的那条路就断了如果你没有先把后一个节点记下来后面就再也走不到链路剩余部分了。就像你在一根绳子上打结先得用手捏住你还要走的那个绳头再转头系结。手动模拟一遍链表 1 - 2 - 3整个过程应该是cur1保存next21-nextNULLprev1cur2cur2保存next32-next1prev2cur3cur3保存nextNULL3-next2prev3curNULL最终prev指向 3链表变成了 3 - 2 - 1。这个推演建议自己拿三个便利贴当节点摆在桌上亲手转一次指针方向胜过读十遍代码。递归反转也能写但递归的问题在于链表长了容易栈溢出而且递归的思路对初学者不友好。核心逻辑是“先把后面所有节点反转好再让当前节点的下一个节点的 next 回头指向当前节点”自己画图体会会更清楚我一般在面试里优先写迭代版本。4.2 环检测快慢指针的思路一个链表如果某个节点的 next 指向了前面某个节点就会形成环遍历永远走不完。检测一个链表有没有环最经典的办法是快慢指针一个指针每次走一步另一个指针每次走两步。如果链表有环两个指针最终会在环里相遇如果没有环快指针会先走到 NULL。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; // 无环 }为什么快指针一定要走两步如果快指针也走一步那永远和慢指针保持同样的距离根本不可能追上。走两步时每轮循环两个指针的距离会缩小 1所以必定会相遇。这个“距离差”的思想在后面很多双指针题目里都会用到。这里还有一个小细节循环条件必须同时判断fast ! NULL和fast-next ! NULL。如果链表就只有两个节点且成环fast-next可能已经不是空如果没有环快指针走到末节点后fast-next就是空。少一个判断就可能访问空指针。判断顺序上先判断fast ! NULL再判断fast-next ! NULL利用短路求值保证后面那个不会在空指针上取成员。4.3 合并两个有序链表合并两个有序链表也是刷链表题绕不开的一道题。思路和归并排序很像两个指针分别指向两个链表的头部每次比较两个节点的大小把小的那个接到结果链表的尾部然后对应指针后移。用虚拟头节点会让代码干净很多Node *mergeTwoLists(Node *l1, Node *l2) { Node dummy; dummy.next NULL; Node *tail dummy; 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; } if (l1 ! NULL) { tail-next l1; } else { tail-next l2; } return dummy.next; }这里我在栈上创建了一个 node 作为虚拟头节点dummy它的 next 才是真正结果的第一个节点。返回dummy.next而不是dummy因为dummy是栈上的临时变量函数返回后就失效了你只能要它的 next 指针。合并过程的时间复杂度是 O(mn)m 和 n 分别是两条链表的长度因为每条链表只被遍历了一遍。你能看到虚拟头节点在这里又立功了如果一开始就判断“结果链表的头到底来自 l1 还是 l2”这里就得写两套分支。有了 dummy第一个被接的节点也是“普通情况”代码统一了。5. 效率和选型链表和数组到底谁更快5.1 时间复杂度对比表很多人以为链表时间复杂度和数组一比就“全面胜出”其实这是误解。我列一张常用操作的对比表操作数组单链表随机访问O(1)O(n)在头部插入O(n)整体后移O(1)在尾部插入O(1)不考虑扩容O(n)要找到尾在已知位置后插入O(n)后移O(1)改指针删除已知位置O(n)前移O(1)改指针按值查找O(n)O(n)注意链表在“头部插入”是 O(1)但数组在头部插入要 O(n)这是链表最强的场景之一。而链表在“尾部插入”其实并不快如果还要维护一个尾指针那也得 O(1) 才能做到。所以很多工程实现里单链表会额外维护一个 tail 指针专门加速尾部插入。如果你自己实现一个队列用带头尾指针的单链表确实比数组实现起来更自然入队出队都是 O(1)。但如果谈到查找链表完全没有优势。数组可以二分查找链表连“跳到中间”都做不到必须从头走。所以“链表 vs 数组”不是谁替代谁而是谁更匹配你的操作模式。5.2 被低估的“缓存不友好”这也是很多初学者容易忽略的点。时间复杂度只考虑了操作次数没考虑底层硬件的实际行为。现代 CPU 有缓存缓存是按“缓存行”整块加载的。数组内存连续你访问 arr[0] 时CPU 会把它附近的数据一起加载进缓存后面访问 arr[1]、arr[2] 很可能直接命中缓存速度飞快。链表节点是靠 malloc 一个个分配的它们的内存位置分散在各个角落每次访问一个节点CPU 可能要重新从内存加载一个缓存行而加载过程中 CPU 要等内存这个等待远比执行几条指令耗时。所以实际工程里同样是 O(n) 的遍历数组往往比链表快一个数量级尤其在数据量大的时候。我做过一个小实验用 100 万个整数分别存进数组和单向链表然后按顺序求和数组耗时通常只有链表的几分之一甚至更低。这提醒我们算法题里说“链表插入 O(1)”是对的但真实世界里还要考虑缓存命中和内存分配的开销。5.3 实际工程中的链表形态虽然链表的缓存表现不理想但在很多场景它依然无可替代。常见的有哈希表的拉链法每个桶后面挂一条单链表碰撞时把新元素往链表头一插O(1)。内存分配器用空闲链表维护可用的内存块分配和释放时把块从链表取下或插进去。撤销/重做功能编辑器里的操作历史通常是双向链表可以沿 prev/next 在两个方向来回走。LRU 缓存淘汰经典实现是“哈希表 双向链表”哈希表提供 O(1) 查找链表维护访问顺序访问过的节点移到头部尾部就是要淘汰的。文件系统的目录结构、进程调度器等也大量使用链表或链表变种。你会发现工程里真正普遍使用的是双向链表因为很多操作需要前后两个方向都能走。单链表最大的价值在于它的思想简单是理解后续所有链表变种的基石。搞清楚单链表双向链表、循环链表基本就是再加一个指针的事。6. 实战避坑检验你真正掌握的五个细节6.1 空指针与悬垂指针的自查习惯链表崩溃九成以上和空指针有关。常见场景包括对空链表调用插入函数、遍历结束后拿着 p 直接访问 p-data、删除节点后没有更新前驱的 next 导致出现了悬垂指针。悬垂指针指向的内存已经被释放但它还“看起来”有个地址访问时结果不可预测。我排查这类问题的习惯是先看代码里有没有“连续两次解引用同一个指针”的地方比如p-next-data这里其实隐含了两层p 不能为空p-next 也不能为空。两层空任何一个出问题都崩。写代码时我尽量把这种链条拆开判断或者在循环条件里先判断 p 本身。6.2 free 之后指针要置空吗C 语言里free(p)只释放 p 指向的内存p 本身的值不会被清空。free 之后你如果还下意识写一句p-data那就是非法访问而且这种 bug 时灵时不灵特别难查。为了安全我在释放指针后都会立刻把它置空free(tmp); tmp NULL;释放的是节点但要防止有多个指针同时指向那块内存比如 prev 的 next 和 cur 都指向同一个节点。free 完 cur理论上 prev-next 也已经改走不会再用旧地址。但这种“多个指针指向同一地址”的场景很容易在修改代码时埋雷。处理原则是释放内存后所有指向它的指针都要确保不再被使用。6.3 排查链表问题的“最小复现法”链表 bug 有个特点打印日志经常看不出问题因为地址信息杂乱无章数值变化又太快。我自己的调试路径是先把链表缩减到最小复现长度比如三个节点A-B-C。在纸上画出操作前后的指针关系每一步都标出谁指向谁。对照代码一行一行执行把每次赋值当成“把箭头从旧目标移到新目标”。加一个打印函数在操作前后各打印一次链表用p p-next推进确认指针链接没有断。三步能解决八成的问题。有一次我排查一个反转链表死循环最后发现是忘了在循环里推进prev指针导致 prev 一直停在原地cur 转了一圈又绕回来。这种问题如果只看代码很难一眼看出来但画图后“指针走着走着就卡住了”是一目了然的。6.4 面试里最容易被问的细节链表面试题虽然模式固定但有几个高频追问值得提前准备。一是“为什么删除节点要知道前驱”大部分人会回答“因为要修改前驱的 next”但面试官往往还会追问“如果不给前驱有别的办法吗”这就引出了一种技巧把当前节点的值换成后一个节点的值然后删除后一个节点。这个技巧只适合删除“非尾节点”但能体现你对指针关系的灵活理解。二是“为什么链表不适合二分查找”根本原因是链表不支持随机访问无法在 O(1) 内跳到中间所以就算链表有序二分查找也无法高效实现。三是“带头尾指针的链表要注意什么”答案是删除尾节点时你必须知道它的前驱而有尾指针不代表你能 O(1) 拿到前驱这是单链表天生的限制。这些问题没有标准答案但都指向同一件事你是否真的理解了“单链表每一步只能通过 next 往前走”这个核心约束。我自己带过不少同学观察下来链表学得好不好最有效的判断标准不是能不能背出代码而是能不能在纸上把一次插入、删除的指针变化画明白。单链表的内容说多不多说少不少但只要抓住“节点含数据域和指针域、操作靠前驱、边界看空指针”这三条主线后面学双向链表、循环链表、跳表都会非常顺。如果你现在正要手写一个链表我的建议是先别急着开编辑器拿一支笔画一画画明白了代码一次跑通是大概率事件。