工作这几年我面试别人时特别喜欢问一道链表反转题。不是故意刁难而是链表创建使用这件事最能把一个人对指针、内存、边界条件的理解水平暴露出来。表面上它只是定义几个节点、改几个 next 指针可一旦出现一个空指针、一次丢链整个程序就像多米诺骨牌一样倒下去。与其背模板不如把链表的来龙去脉真正搞懂。这篇文章围绕链表创建使用展开从 C 语言结构体链表基本语法讲起会依次拆解 C、C、Java、Python 四种语言里的链表写法再带你亲手跑通链表遍历、链表插入、链表删除和逆置链表最后聊到循环单链表、嵌入式链表代码示例以及基于链表的两个集合的差集问题。无论你是刚做完单链表基本操作实验的大学生还是准备面试的在职工程师这篇文章都能给你一套可以反复参考的实操思路。1. 先从底层理解链表一张用指针串起来的“火车车厢图”很多人学链表第一反应是去背代码模板这是最大的误区。链表的核心不在代码本身而在于它和数组走的是两种相反的内存策略。先把这个理解透了后面写代码、调 bug 才能做到心里有数。1.1 数组和链表内存布局上的两种哲学数组要求一段连续的内存空间。你声明int arr[10]编译器就要保证这 10 个 int 在内存里是挨着的。好处是随机访问很快想取第 7 个元素直接arr[6]就好CPU 做一次加法就能算出它的地址时间复杂度是 O(1)。坏处也很明显在中间插入一个元素要把后面所有数据整体后移数组扩容时经常要重新找一块更大的连续内存再把旧数据整体拷贝过去。链表完全反过来。它不要求内存连续每个节点可以散落在堆上。每个节点里有一个数据域保存业务数据有个指针域保存下一个节点的地址。要创建链表本质上就是创建一堆零散的节点再用指针把它们按顺序串起来。所以有人说链表是一张“指针连成的网”这话很贴切。打个生活化的比方数组像电影院的连排座椅座位号固定、紧挨着找 5 号座一眼就能看到链表像火车车厢每节车厢可以挂在任意位置想找到第 5 节车厢你得从头一节一节数过去。但要在第 2 节和第 3 节之间加挂一节新车厢你只需要断开两节车厢的连接再插进去其他车厢全程不用动。这个特性带来了链表最核心的复杂度结论按下标取值是 O(n)但在已知前一个节点位置的前提下插入和删除都是 O(1)。换句话说链表牺牲了随机访问换来了“任意位置插入删除”的高效率。1.2 都 2025 年了链表为什么还没被淘汰不少新手会有疑问高级语言里都有ArrayList、Vec、List谁还傻乎乎自己写链表我工作中还真离不开链表至少这几个场景是链表的固定舞台嵌入式开发里内存碎片和动态内存分配非常敏感。系统往往不能用一块大的连续内存去做数组反而会把小块的、零散的堆内存用链表组织起来。很多嵌入式设备的任务队列、定时器列表本质就是链表。操作系统内核里进程描述符、文件描述符、缓冲区列表大量使用双向链表或者循环链表。你用 C 语言写驱动程序时也常常需要嵌入式链表代码示例来组织设备对象。高级语言内部也有链表的身影。Java 的HashMap在哈希冲突时同一个桶位就用链表存数据Python 的字典虽然主要靠开放寻址但很多底层结构同样会用到链式思路。需要频繁在头部插入、删除的场景链表是天然的好选择。实现一个栈、队列、缓存淘汰策略链表都很顺手。所以别再觉得链表是教科书里过时的东西。它只是换了个方式留在现代软件里真正吃透它对你理解其他数据结构非常有帮助。2. 链表创建的核心节点定义、头指针和内存分配链表的创建是整个使用的基础。这一步最常见的问题是定义节点时不知道成员该怎么写或者在创建空表时没有处理好头指针。我建议先从 C 语言开始因为 C 语言里你能看到内存分配、释放的全过程理解会最深入。2.1 C 语言结构体链表基本语法C 语言创建单链表第一步是定义节点。最常见的写法是用结构体struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 };这个结构体里有一个数据成员int data一个指针成员struct Node *next。关键点是next的类型必须是struct Node *也就是指向同类型节点的指针。没有这一步节点之间就“串”不起来。定义好节点后创建空表只需要一个头指针struct Node *head NULL;head指向链表的第一个节点。空表就是head NULL这是一个非常干净的状态。接下来创建第一个节点并把它放到链表的头部struct Node *node (struct Node *)malloc(sizeof(struct Node)); if (node NULL) { // 处理内存分配失败 return -1; } node-data 42; node-next head; head node;这里有几个细节值得新人注意malloc只负责分配内存不会初始化结构体成员。所以node-data和node-next必须手动赋值不能想当然地认为它们是 0。malloc之后必须检查是否为NULL。在内存受限的嵌入式环境里分配失败不是稀罕事。把node-next赋成旧的head再更新head node这是典型的头插法。头插法的好处是插入操作永远是 O(1)而且不需要遍历整个链表找尾巴。2.2 C、Java、Python 里的链表创建方式不同语言对链表的实现核心思想完全一样只是语法和内存管理方式不同。C 里可以用结构体也可以加构造函数让节点初始化更省事struct Node { int data; Node *next; Node(int d) : data(d), next(nullptr) {} };这里的next是Node *构造函数里的next(nullptr)把指向空地址这件事表达得很明确。用new Node(42)创建节点时data和next都会按你定义的构造函数初始化。Java 和 Python 没有指针语法于是把节点定义成一个类引用类型天然相当于“指针”public class Node { int data; Node next; public Node(int data) { this.data data; this.next null; } }class Node: def __init__(self, data): self.data data self.next None你看结构完全一致数据域 指针域。Java 的next和 Python 的next都是引用类型指向另一个节点对象本质上就是指针只是你不用亲手管理内存。Java 有 GCPython 也有引用计数和 GC所以少了一堆free/delete的烦恼但也少了一层“内存到底什么时候释放”的感知。我把这四种语言的创建方式放到一起对比一下语言节点定义形式内存管理初始状态Cstruct Node { int data; struct Node *next; }手动 malloc/free手动置 NULLCstruct Node { int data; Node *next; Node(int d):... }使用 new/delete 或智能指针构造函数初始化Javaclass Node { int data; Node next; }JVM GC见 new 自动置 nullPythonclass Node: def __init__(self, data): ...引用计数 GCnext None从工程角度看我建议新手先在 C/C 里把链表的创建、遍历、插入、删除完整写一遍至少练到能不假思索地处理野指针。等你在 C 语言里吃过亏再去用 Java 或 Python 就会觉得链表异常简单。2.3 头节点到底该不该要哑节点是个好东西链表创建时还有一个设计选择要不要加一个“哨兵节点”也叫“带头节点”。带头节点的意思是head指向一个不存业务数据的空节点真正的第一个数据节点是head-next。这个节点的存在能让空链表和非空链表的操作统一起来。举个例子删除第一个节点时不带头节点你发现要删的是头节点必须特殊处理把head更新成head-next。带头节点不管删谁逻辑都是找前一个节点然后改它的next。删除“第一个”数据节点也只是next指向的节点处理方式和删除中间节点一模一样。我在实际项目中偏向带头节点空表判断变成head-next NULL代码里不用到处写if (head ...)这种分支。缺点是多分配了一个节点但一个节点才几个字节对绝大多数场景无所谓。直到今天我在写链表删除类函数时仍然会先在函数里定义一个局部的哑节点来简化逻辑。struct Node *deleteByValue(struct Node *head, int value) { struct Node dummy; dummy.next head; struct Node *prev dummy; struct Node *cur head; while (cur ! NULL cur-data ! value) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; free(cur); } return dummy.next; }注意这里用了栈上的局部变量dummy不额外申请堆内存。它只在函数内部存在函数返回时head已经从dummy.next里拿回来了。这种技巧面试、竞赛里都用得上建议多练几遍。3. 链表使用遍历、插入、删除、逆置一次过创建只是第一步链表真正麻烦也是最容易出错的是使用阶段。这一节我按“遍历 - 插入 - 删除 - 逆置”的顺序讲每一步都附上可以运行的思路和易错点。3.1 链表遍历循环条件是关键链表遍历看起来简单翻车率却很高。核心代码就一个循环void printList(struct Node *head) { struct Node *cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }重点在于循环条件是cur ! NULL而不是cur-next ! NULL。很多新手会把条件写成while (cur-next ! NULL)然后发现最后一个节点没打印。原因很简单当cur已经指向最后一个节点时cur-next确实是 NULL循环提前结束了最后一个节点的数据还没来得及处理。真正的高手写遍历时脑子里想的只有两件事会不会访问到空指针退出循环后cur停在哪个位置另外提一个高频扩展技巧快慢指针。比如找链表中间节点可以让slow每次走一步fast每次走两步struct Node *middleNode(struct Node *head) { struct Node *slow head; struct Node *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这个写法之所以成立是因为当fast到达链表末尾时slow正好走了一半。变换条件还可以用来判断链表是否有环fast如果追上了slow说明有环。这也说明链表遍历不仅是“从头到尾打印”这么简单它背后的指针移动节奏才是高级算法的基础。3.2 链表插入头插、尾插、中间插的正确顺序插入操作得分三种情况看因为它们的代码细节差别很大。头插法效率最高不需要找尾巴struct Node *insertAtHead(struct Node *head, int value) { struct Node *node (struct Node *)malloc(sizeof(struct Node)); node-data value; node-next head; head node; return head; }注意顺序是先把node-next指向旧head再更新head。如果先执行head node原来的链表头就找不到了整条链直接丢了一半。尾插法需要先找到最后一个节点struct Node *insertAtTail(struct Node *head, int value) { struct Node *node (struct Node *)malloc(sizeof(struct Node)); node-data value; node-next NULL; if (head NULL) { return node; } struct Node *cur head; while (cur-next ! NULL) { cur cur-next; } cur-next node; return head; }这里循环条件用cur-next ! NULL退出循环后cur就是最后一个节点然后再挂新节点。如果循环用成了cur ! NULL那退出时cur已经是 NULL你就找不到能接新节点的那个对象了。如果你经常要做尾插建议额外维护一个tail指针直接指向链表尾部尾插时间复杂度就能从 O(n) 降到 O(1)。嵌入式里很多驱动就是这么干的否则数据一多每插一次都遍历全表性能要吃大亏。中间插在某个节点后面插入核心是两步顺序不能乱node-next prev-next; prev-next node;假装prev是你要插入位置的节点。第一步先让新节点指向prev的后继第二步再让prev指向新节点。这个顺序非常重要因为如果先执行prev-next nodeprev原来的后继就找不着了新节点就只能断在中间。我把这称为“先牵住再松手”原则。3.3 链表删除释放内存和边界条件缺一不可删除一个指定值的节点代码里最容易出问题的点有两个一是找不到节点二是删的是头节点。struct Node *deleteNode(struct Node *head, int value) { struct Node *cur head; struct Node *prev NULL; while (cur ! NULL cur-data ! value) { prev cur; cur cur-next; } if (cur ! NULL) { if (prev NULL) { head cur-next; } else { prev-next cur-next; } free(cur); } return head; }这段代码的思路是先找到要删的节点cur同时记录它的前驱prev。删除时让prev-next绕过cur直接指向cur-next。如果prev是 NULL说明删除的恰是头节点这时要更新head。两个细节我在实际中吃过亏free(cur)之后cur本身成了悬空指针不要再通过cur访问任何数据。free不改变cur保存的地址值只是这块内存被释放继续用就是未定义行为。返回值必须用新head带回。链表删除后头节点可能会变所以函数最好返回新的头节点或者用二级指针来操作头节点。3.4 逆置链表迭代和递归两套思路逆置链表是面试出现率最高的链表题也是检验链表基本功的试金石。迭代法的核心是一个三指针轮转prev、cur、next。每次把cur-next指向prev然后整体右移一个位置。最终prev就是新的头节点。struct Node *reverse(struct Node *head) { struct Node *prev NULL; struct Node *cur head; while (cur ! NULL) { struct Node *next cur-next; // 先保存后继 cur-next prev; // 反向链接 prev cur; // 指针右移 cur next; } return prev; }这一步里struct Node *next cur-next;出现在反转之前非常关键。如果不先保存等到cur-next被改成prev原本的后继就丢了后面的链表节点全部失联。Python 单链表逆序写法思路完全一样只是少了指针符号def reverse(head): prev None cur head while cur: nxt cur.next # 保存下一步 cur.next prev # 反向 prev cur cur nxt return prev # 新头递归法看起来更简洁但对初学者不太友好struct Node *reverseRecursive(struct Node *head) { if (head NULL || head-next NULL) { return head; } struct Node *newHead reverseRecursive(head-next); head-next-next head; head-next NULL; return newHead; }核心逻辑是先把head-next为头的子链表反转得到新链表的头newHead。此时原来的head-next恰好变成子链表的尾节点所以让head-next-next head再把head-next置空head就变成了新链表的尾节点。递归法代码短但递归深度等于链表长度。链表很长时可能栈溢出。我平时优先用迭代法它空间复杂度是 O(1)更稳健也更容易边写边推理。4. 进阶变种循环单链表、嵌入式链表和集合差集基础的单向链表练熟之后真正有意思的是它在各种场景里的变体。这一节挑三个最具代表性的来聊单循环链表、嵌入式链表代码示例、基于链表的两个集合的差集。4.1 单循环链表让尾节点亲手把自己绕回去循环单链表也叫单循环链表它的特别之处是最后一个节点的next不再指向 NULL而是指向头节点。从任意一个节点出发都能绕回自己所在的环。创建循环链表时关键代码就是把尾节点指向头节点// 假设 tail 一直维护着尾节点 tail-next head;遍历循环链表时终止条件不能再是cur ! NULL因为环里不会有 NULL。正确做法是用cur ! head判断或者用do...while。void printCircularList(struct Node *head) { if (head NULL) return; struct Node *cur head; do { printf(%d - , cur-data); cur cur-next; } while (cur ! head); }为什么用do...while因为一开始cur head如果用普通while会直接跳过整个循环一个节点都打不出来。用do...while至少能保证先访问一次。循环链表很常见的应用是“约瑟夫环”一群人围成一圈报数每报到某个数就淘汰一个人继续循环。这种问题用循环链表模拟最自然因为“绕圈”本来就是循环链表的刻板行为。轮转调度Round-Robin里操作系统给每个进程一个时间片运行完就移到队尾也是一种循环链表思维。4.2 嵌入式链表代码示例侵入式设计嵌入式系统和内核代码里的链表和教科书的写法不太一样。教科书链表把数据放进节点比如struct Node里面有int data但嵌入式里的链表常常反过来业务结构体自己包含一个链表节点成员。这种设计叫“侵入式链表”。举个例子你想管理一堆设备对象struct list_node { struct list_node *next; }; struct device { int id; char name[32]; struct list_node node; // 节点嵌在业务结构体内 };创建时不需要单独为链表节点分配内存只需把struct device里的node成员串起来。这样链表天然和业务对象绑定内存消耗更少也避免在无人值守的系统上反复 malloc/free。嵌入式里更常见的是双向环形链表比如 Linux 内核里的list_head。它的好处是遍历可以向前向后操作宏统一代码冗余少。比如初始化链表头struct list_node head; head.next head; // 空环头节点指向自己插入和删除只需要处理自身和前驱后继的指针不用管是不是头节点。这也是嵌入式链表代码示例里最常见的形态先让头指向自己形成空环再在环上不断插入节点。我做嵌入式项目时最开始的习惯是使用传统“数据在节点里”的链表后来发现一旦任务对象要被多次排队或者从链表中删除传统做法要频繁申请和释放节点内存碎片增加很快。换成侵入式链表之后删除节点只是从链上摘下来业务对象的内存仍由任务池统一管理整体稳定多了。4.3 基于链表的两个集合的差集一道很好的课堂实验题“基于链表的两个集合的差集”是很多学校实验课会出的题目也是热词里出现频率很高的一个点。集合差集的定义是集合 A 减去集合 B留下那些属于 A 但不属于 B 的元素。如果链表是无序的最简单的做法是两层循环外层遍历 A 的每个节点内层逐个去 B 里比对。这个思路直观但时间复杂度是 O(m * n)m 和 n 分别是两条链表的长度。实验场景里数据量小可以跑通数据一旦放大性能很难看。更高效的解法是先把链表排序。两条有序链表求差集可以用一次归并式的线性遍历完成假设 A 和 B 都是递增有序链表分别用pa和pb指向当前节点while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { // A 里的这个值一定不在 B 中加入结果 addToResult(pa-data); pa pa-next; } else if (pa-data pb-data) { // 两边相等这个值属于交集跳过 pa pa-next; pb pb-next; } else { // pa-data pb-dataB 太小了继续往后找 B pb pb-next; } } // 如果 A 还有剩余说明这些元素都不在 B 中 while (pa ! NULL) { addToResult(pa-data); pa pa-next; }这个算法的时间复杂度是 O(m n)因为有两条链表的指针都只往前走不会回头。处理完残留在 A 中的尾巴后结果链表就是 A - B 的差集。面试或者实验里遇到这类题目先别急着写嵌套循环。问清楚两个集合是否有序如果无序考虑先排序排序本身可以用归并排序法因为链表找中点、合并都方便。5. 链表的坑与调试技巧把崩溃率压到最低链表代码的调试可能是所有数据结构里最容易让人崩溃的。这里我把实际代码中常见的问题整理成一个速查表再分享我自己的调试方法。5.1 常见错误清单错误类型现象原因解决办法空指针访问段错误没有检查head NULL每次操作先判空循环条件写错最后一个节点没处理用cur-next ! NULL改成cur ! NULL指针丢失链表断成两截中间插入/删除顺序写错先保存后继指针内存泄漏可用内存越用越少删除节点没释放内存C/C 里 free/delete循环链表死循环程序卡死不退出遍历条件错误用cur ! head判断递归过深栈溢出反转或复制用递归改成迭代看起来都是基础问题但我在真实项目里见过这些错误的频率远比想象中高。尤其是指针丢失几乎每个练链表的人在中间插入那一步都翻过车。5.2 我的调试三板斧第一招先画图再写代码。在纸上画 5 个小方块代表节点写上data值圈出next指向谁。删除、反转这类操作每一步把箭头重新画一遍很多错误一眼就能看出来。第二招写一个打印函数。别嫌它基础链表调试最有用的永远是一个能打印整条链、并在每个节点之间显示箭头的函数。尤其是反转后的链表打印出来的输出是验证算法正确性的第一依据。第三招用最小样例测试。不要拿几百个节点去调那样只会把错误混在一起。就用 0 个节点、1 个节点、2 个节点的链表跑操作然后再放大数据。空表、单节点、环形边界往往藏了 80% 的边界 bug。有条件的还可以开地址消毒器AddressSanitizer编译时加-fsanitizeaddress内存越界、释放后使用一抓一个准。嵌入式环境里没有这套工具那就靠手动free并置空指针以及严格的内存池管理来兜底。5.3 单链表基本操作实验的实操步骤如果你正在做“单链表的基本操作实验”我建议按这样一个标准流程走完每一步都要看到输出定义结构体节点初始化一个空链表head NULL。头插法插入 3 个数据1、2、3打印结果应该输出3 - 2 - 1 - NULL。尾插法插入两个数据4、5打印结果应该输出3 - 2 - 1 - 4 - 5 - NULL。删除值为 1 的节点打印结果应该输出3 - 2 - 4 - 5 - NULL。在值为 2 的节点后插入节点 100打印结果应该输出3 - 2 - 100 - 4 - 5 - NULL。执行逆置链表打印结果应该输出5 - 4 - 100 - 2 - 3 - NULL。每做一步就在纸上画出当时的链表状态再和程序输出对比。只要能把这六步跑通单链表的创建、遍历、插入、删除、逆置就基本过关了。结尾最后分享一个我自己保持了很多年的习惯凡是写可能删除节点的链表函数优先加一个局部哑节点凡是调试链表问题先画图再开编译器。这两件事让我面对链表时的崩溃率低到可以忽略。链表创建使用这件事本质上就是不断和指针、边界条件打交道。刚练习时出错非常正常不要慌把每次段错误都当作一次理解内存的机会。等你看到Segmentation fault不再心头一紧而是平静地打开画板和打印函数时你的链表基本已经练到家了。