开头先交代一个背景我辅导过不少学生的数据结构实验发现链表这一章几乎每个人都会卡一次。不是说它有多难而是链表的操作天然依赖“指针/引用”这种间接跳转的思维方式和数组那种“按下标直取”的直觉完全相反。你翻开课本看代码似乎每行都认识合上书自己写单链表插入十个里有七个会写错前驱指针的衔接。这篇内容我按自己实际讲课和调试的经验来写把链表从结构体定义、遍历、插入、删除、逆序到双链表和循环链表串一遍C语言和Python两种写法都会给出可直接用的代码和踩坑记录。适合正在上数据结构课、准备考研机试、或者刷LeetCode链表题总超时的同学看完至少能解决“代码跑不通”和“懂了但写不对”这两类问题。1. 链表的本质为什么数组已经够用还要造一个它先搞清楚一个最底层的问题链表到底在链什么。数组的逻辑是“连续的盒子”你声明一个int a[10]编译器就给你划拉一块连续内存下标就是盒子的编号。访问a[3]本质是a的起始地址 3 * sizeof(int)一次加减就能算出位置所以数组随机访问是O(1)。代价是什么中间插入一个元素需要把后面所有元素往后挪时间复杂度O(n)而且数组长度是固定的想扩容得重新开辟一整块更大的内存再复制过去。链表走的是另一条路彻底不保证内存连续每个节点单独申请然后用指针把自己和下一个节点串起来。就好比火车车厢车厢之间靠挂钩连接车厢本身停在哪个轨道并不重要只要挂钩不脱整趟车就能跑。你要在中间加一节车厢只需要把前后两节车厢的挂钩解开再重新挂上后面的车厢完全不需要挪位置。这就是链表插入删除快的本质原因——修改几个指针字段时间复杂度O(1)。查找则要从头到尾顺着挂钩一个个走没法跳跃O(n)。我来补一个非常关键的概念区别“不带头结点”和“带头结点”这两种形式几乎是初学者第一道坎。不带头结点的链表头指针直接指向第一个数据节点。一开始链表为空时头指针是NULL。插入到第一个位置时你修改的是头指针本身而不是某个节点的next字段所以函数里经常要传二级指针struct Node **head或者靠返回值来更新头指针。带头结点的链表额外分配一个不存有效数据的节点作为头结点让它的next指向真正意义上的第一个数据节点。哪怕链表为空头结点也始终存在头指针始终非空。这样一来插入和删除第一位的逻辑和插入删除中间位置完全统一不需要单独特判。我的建议非常明确写C语言的单链表时默认都带头结点除非题目明确说“不带头结点”。不是说不带头结点不好而是带头结点能把边界条件从三个降成一个。这会直接决定你调试时流的泪多还是少。2. C语言单链表从结构体到基本操作2.1 结构体定义先想清楚节点里要装什么C语言定义链表节点用的是结构体这是整个链表实验的基础。很多同学上来就写结果连节点的字段都没想清楚一个节点至少包含两部分一个是数据域就是你真正要存的东西可以是整数、字符甚至另一个结构体另一个是指针域存的是下一个节点的地址类型必须是“指向本结构体的指针”。typedef struct Node { int data; // 数据域先拿最简单的int练手 struct Node *next; // 指针域指向下一个同类型节点 } Node;这里有个比较隐蔽的语法点在结构体内部声明next指针时由于typedef还没有生效必须写全struct Node *next。等typedef结束之后你才能用Node这个别名去声明变量、参数和返回值。很多C语言初学者会在这个地方报错然后一脸茫然其实记住一句口诀就好结构体内部引用自己只能用结构体本身的原始名字。如果你要做“在指定位置插入建立单链表”的实验通常还会扩展成“带头结点的尾插法”和“带头结点的头插法”两种建立方式。它们唯一的区别就是新节点接在链表的哪个位置。2.2 带头结点单链表的插入重在找前驱插入操作是单链表里首要的操作也是理解整张链表的钥匙。先给一段完整的、用尾插法建立带头结点单链表的代码#include stdio.h #include stdlib.h Node *createList() { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; return head; } Node *getLast(Node *head) { Node *p head; while (p-next ! NULL) { p p-next; } return p; } void insertTail(Node *head, int value) { Node *last getLast(head); Node *newNode (Node *)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; last-next newNode; }注意到没有尾插法每次都要遍历到最后一个节点所以建立一个n个节点的链表时间复杂度是O(n²)。如果要高效地建立链表应该额外用一个tail指针记录链尾每插入一个节点直接更新尾指针这样建表时间降到O(n)。这是我反复强调的一个点——很多实验报告只要求“能跑通”但面试和机试考的是“时间复杂度是否最优”。在指定位置插入我把关键逻辑抽出来说。假设要在第i个位置插入值为value的节点你需要做的事是从head出发移动i-1次让指针p指向第i-1个节点也就是新节点的前驱。申请新节点newNode把value放进去。让newNode-next p-next这句话把新节点挂在“前驱原本的下一个节点”前面。让p-next newNode前驱的next改为指向新节点。代码是int insertAt(Node *head, int pos, int value) { Node *p head; int i 0; while (p ! NULL i pos - 1) { p p-next; i; } if (p NULL) { printf(position invalid\n); return -1; } Node *node (Node *)malloc(sizeof(Node)); node-data value; node-next p-next; p-next node; return 0; }这个代码有两处初学者最容易写反一是忘了把p移动到前驱直接从头节点开始判断二是在第3步和第4步里把两句的顺序写反。这里我要重点强调node-next p-next必须写在p-next node之前。如果先执行后者前驱的next已经被改成新节点了原本的下一个节点地址就丢了后面再想接就接不上链表直接断裂。这类错误用一句话概括就是牵扯到两个指针修改时先保存要修改的旧值再赋新值。2.3 删除操作的三种边界删头、删尾、删中间删除操作的核心思路和插入一样也是找前驱。但要格外小心三种边界情况。int deleteNode(Node *head, int value) { Node *p head; while (p-next ! NULL p-next-data ! value) { p p-next; } if (p-next NULL) { return -1; // 没找到 } Node *target p-next; p-next target-next; free(target); return 0; }这段代码删除的是第一个值为value的节点。它的巧妙之处在于全程记录的是“目标节点的前驱”这比记录“目标节点”本身要方便得多因为单向链表回不到前面去。删除时让前驱的next绕过目标节点指向目标节点的后继然后free掉目标节点。我见过很多漏掉free(target)的同学实验代码跑完内存泄漏一大片。C语言不像Java/Python有垃圾回收你malloc出来的节点不释放这块内存在程序结束前永远占用。链表实验的体量小可能看不出问题但养成这个坏习惯进真实项目内存泄漏会变成线上事故。删节点必须配套free就像借了钱必须还。删除头部节点时因为有头结点存在头结点本身不能删删的是头结点后面的第一个节点。这个时候p headtarget head-next逻辑和上述代码完全一样不需要特判。这是带头结点方案最大的好处你可以体会一下如果是不带头结点删第一个节点时头指针要更新函数参数得用二级指针代码的复杂度立刻升一个级别。2.4 遍历、清空和逆置三个看似简单实则考人的操作链表遍历是最好写的一个循环走到底void traverse(Node *head) { Node *p head-next; // 跳过带头结点的空头 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这里有个细节带头结点的链表遍历从head-next开始不带头结点的遍历从head开始。上课实验时经常有同学把头结点也打印出来数据里多出一个随机初始化的值排查半天才发现是这个原因。清空链表不少人以为把head-next NULL就完事了。大错特错。你只是把链表的入口封了但链表上每一个节点的内存都还在全部泄漏。正确的清空是逐个释放void clearList(Node *head) { Node *p head-next; while (p ! NULL) { Node *temp p; p p-next; free(temp); } head-next NULL; }注意这个循环里必须先让p跳到下一个节点再去free当前的temp。顺序反过来就出大事free(p)之后p-next已经是无意义的值你再拿它去跳转轻则拿到脏数据重则野指针崩溃。这里的经验是要释放的节点和要继续前进的指针必须分开两个变量。逆置链表也就是常说的单链表逆序。面试和机试几乎必考我给你讲两种写法。一种是迭代法三指针顺序翻转。思路是逐个把指针掉头让每个节点都指向自己的前驱头结点最终指向原来的尾节点void reverseList(Node *head) { Node *prev NULL; Node *curr head-next; while (curr ! NULL) { Node *next curr-next; curr-next prev; prev curr; curr next; } head-next prev; }这个代码的核心是Node *next curr-next;必须先保存后驱。你翻转curr-next之后原来的后驱就找不到了所以要在翻转之前就把下一步的地址锁住。这里叫“三指针法”变量的作用分别是curr是当前要翻转的节点prev是翻转后应该指向的新邻居next是锁住的下一个要处理的节点。另一种是递归法很多人觉得递归清奇但我建议考试时谨慎使用因为递归深度就是链表长度链表长几万条时会爆栈。我一般跟学生说面试写逆序优先三指针迭代考场上最稳。Python 版逆序我们在后面讲因为 Python 的写法完全不同没有指针概念用的是链式引用的重绑定。3. Python单链表的逆序实现与面向对象封装3.1 类结构定义Python 没有指针但类对象的引用天然就是“指向”这让你可以用更直观的方式复刻链表。一个节点class Node: def __init__(self, data): self.data data self.next None一个链表class LinkedList: def __init__(self): self.head None def append(self, data): if self.head is None: self.head Node(data) return p self.head while p.next is not None: p p.next p.next Node(data)注意这里self.head None对应的是不带头结点的单链表。Python 这门语言风格偏向简洁和“显式优于隐式”在数据结构实训里用不带头结点的写法更常见。这也是和前面 C 语言示例刻意区分开来的原因让你两个方向都能驾驭。Python 链表的好处是调试直观你可以在Node类里重写__repr__直接把整条链的列表形式打印出来肉眼检查而不是像 C 语言那样只能 printf 一个字段。class Node: def __init__(self, data): self.data data self.next None def __repr__(self): return fNode({self.data}) - {self.next!r} if self.next else fNode({self.data}) - None3.2 Python单链表逆序三指针法重写Python 的逆序和 C 语言本质同构只是变量名和语法换成 Python 风格def reverse_linked_list(head): prev None curr head while curr is not None: next_node curr.next curr.next prev prev curr curr next_node return prev这个函数和前面 C 语言的reverseList逻辑完全一致但有个区别值得注意Python 不带头结点所以返回的新头就是原来的尾节点。调用时new_head reverse_linked_list(llist.head) llist.head new_head实际操作中很多同学会写错一个点返回的是prev而不是curr。当循环结束时curr已经变成None链表的新头恰恰是prev也就是原来的尾节点。如果你返回curr得到的永远是空指针/空引用。这个坑我见过太多次了。如果你需要看到逆序后打印的效果可以加一个便利方法把链表转成 Python 列表def to_list(head): result [] p head while p is not None: result.append(p.data) p p.next return result3.3 Python递归逆序给思考加一个快照递归逆序虽然性能不是最好的但理解它有助于你真正消化链表结构。看这段def reverse_recursive(node): if node is None or node.next is None: return node new_head reverse_recursive(node.next) node.next.next node node.next None return new_head核心语句是node.next.next node。这句话的意思是让下一个节点的指针反过来指向当前节点。你从后往前想递归不断走到链表尾部把尾节点变成new_head然后一层层往外拔每拔一层就把经过的节点的指针反向。等到最开始那个head的next被置为None整个链表就翻了个个。举一个具体例子链表1 - 2 - 3。递归到3时返回3本身。回到2这一层执行node.next.next node也就是3.next 2再执行node.next None也就是2.next None。链表变成1 - 2 - 3然后回到1这一层执行2.next 11.next None最终3 - 2 - 1。看逆序完成。Python 逆序在 LeetCode 上还有两种特色写法一种是收集值再重建节点def reverse(self, head): vals [] while head: vals.append(head.val) head head.next dummy ListNode(0) p dummy for v in vals[::-1]: p.next ListNode(v) p p.next return dummy.next这个写法虽然空间复杂度是O(n)不如三指针法的O(1)但理解门槛低。面试时候如果时间紧、脑子乱先写出这个能跑的版本再优化成三指针比卡住不动强得多。能跑通再优化是缓解机试紧张的策略之一。4. 循环单链表和双链表两个高频变化体4.1 循环单链表尾指针为何是点睛之笔循环单链表的定义很简单最后一个节点的next不再指向NULL而是回头指向第一个节点带头结点则指向头结点。它的价值在于从任意一个节点出发都能访问到全部节点尤其适合表达周期性结构。最经典的实验是约瑟夫问题n 个人围成一圈报数到 m 的人出列下一人从1重新报数直到只剩一人。这个场景天然是循环单链表。这里要重点讲一个设计细节用尾指针tail代替头指针head来管理循环链表会让代码更顺。为什么因为循环链表里最后一个节点的next正好指向头结点你拿到尾指针tail-next就是头结点头尾都能在O(1)时间访问到。这相当于尾指针顺便包含了头指针的信息。而只有头指针时找到尾节点需要绕一圈O(n)。对比一下约瑟夫的出列操作频繁发生在“当前节点的当前位置”附近直接从头找会慢得多。// 创建n个节点的循环单链表返回尾指针 Node *createCircle(int n) { Node *head (Node *)malloc(sizeof(Node)); head-next head; // 空循环链表自己绕自己 Node *tail head; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data i; node-next tail-next; tail-next node; tail node; } return tail; }约瑟夫出列逻辑void josephus(Node *tail, int m) { Node *p tail; while (p-next ! p) { // 只剩一个节点时p-next p for (int i 1; i m; i) { p p-next; } Node *out p-next; p-next out-next; printf(out: %d\n, out-data); free(out); } printf(leader: %d\n, p-data); }这个代码里p始终指向出列节点的前驱。你从尾指针出发报数m-1次p就到达出列节点前一个节点然后和普通删除一样处理即可。注意这里的p是“绕着圈走”的循环链表的好处就体现在这里。4.2 双链表向前和向后空间换时间双链表每个节点增加了一个prev指针指向前驱。好处显而易见从尾巴往回走不再需要遍历一整条链O(1) 拿到前驱。删除操作也更加自由——你只需要拿到目标节点本身就能通过target-prev和target-next完成线条的重新绑定不需要像单链表那样必须找前驱。C语言双链表节点定义typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;双链表删除target节点void deleteDNode(DNode *target) { if (target-prev ! NULL) { target-prev-next target-next; } if (target-next ! NULL) { target-next-prev target-prev; } free(target); }这是双链表让人舒服的地方传入一个节点就可以完成删除无需从头找前驱。对比单链表必须从头扫一遍找前驱双链表删除是O(1) vs 单链表O(n)。代价是每个节点多一个指针域内存占用多约一半忽略数据域差异时。这个“空间换时间”是数据结构的通用权衡你以后遇到任何设计都要主动想一想多存一份什么信息能让哪个操作更快Python 双链表节点可以这样写class DNode: def __init__(self, data): self.data data self.prev None self.next None双链表在做“LRU缓存”这类需要频繁访问头部和尾部的场景中很有用LeetCode 146 就是经典例子。如果你做完链表实验想进阶可以做一下 LRU把双链表加上哈希表那种“节点O(1)找到并删除”的手感会让你对双链表的理解上一个台阶。5. 链表常见调试方法、典型错误与自学建议5.1 调试手段可视化是唯一的捷径我给学生辅导时反复强调链表调试靠眼睛看打印出来的“箭头链”不靠冥想。你可以写一个辅助函数把链表打成1 - 2 - 3 - None这样的字符串每步操作后都打印一遍。这就相当于给自己装了一台显微镜哪一步接错了一眼就能看出来。Python 里可以直接在LinkedList类中增加def display(self): p self.head nodes [] while p: nodes.append(str(p.data)) p p.next print( - .join(nodes) - None)C 语言里就写一个printList函数把每个节点地址也顺手打印出来void printListWithAddr(Node *head) { Node *p head-next; while (p ! NULL) { printf([%p] %d - , p, p-data); p p-next; } printf(NULL\n); }顺带一提加%p打地址在排查循环链表有没有成环时非常好用。你会发现某些节点地址重复出现那就是循环了自己或者逆序后产生了环。5.2 高频错误清单每个都是血泪史我总结了链表实操中的高频错误按出现频率排序错误类型现象原因修复办法插入时顺序颠倒链表断成两截丢失后半段p-next node执行在node-next p-next之前先捆绑新节点的后手再解开旧连接删除后未free内存泄漏只改指针不释放节点保存目标指针后跳链接再free遍历不使用临时指针直接拿head遍历导致头指针丢失以为指针是值复制始终用局部p移动不动head边界条件漏判空链表崩溃p-next访问了空指针循环条件写p p-next善用短路口诀逆序后丢节点只翻转一半没有保存next三指针法的第一步永远是保存后驱循环链表退出条件错误死循环拿p-next ! NULL判断循环链循环链用p-next ! head判断举个例子展开第一类错误。假设已有A - B要在 A 后插入 X。正确做法是X-next B然后A-next X。如果你反过来先做A-next X那么 A 和 B 之间的连接就断了X-next又不知道去哪里找 B链表就只剩A - XB 被丢在内存里变成孤岛。这种错误单靠人眼盯代码很难看出来但打印过地址后立刻能发现 B 的地址没有出现在从 A 出发的链条上。5.3 从实验到面试的学习路线建议如果你现在还在上课做实验我建议按这个顺序练先用 C 写带头结点的单链表实现插入、删除、查找、遍历、清空。不要求一次写对但要求能在出错后靠打印地址自己找出问题。把同样的操作用不带头结点的方式再写一遍。体会两种形式的差异重点是带不带二级指针。写逆置迭代法和递归法各一遍然后把约瑟夫问题用循环链表做一遍。用 Python 把上述操作全部重写一遍体会语言风格不同但逻辑同构。如果还有精力去 LeetCode 刷 10 道链表题206反转、21合并、141环形、83去重、876中点、19删倒数第n、24两两交换、160相交、148排序、2两数相加。实战中还有个经验值得分享链表题在面试时要先画图再写码。画图不需要多漂亮把节点画成方框、指针画成箭头用不同颜色标出哪根要改、哪根需要先保存。大多数链表 bug 都能在画图阶段发现根本不用等运行时报错。这个习惯我练了几年几乎成条件反射写的代码一次通过率提高了一大截。6. 最后补一个锦囊C 结构体链表的基本语法落到实处很多学校的数据结构实验用 C 写但用的其实是 C 风格的struct 指针。我给你补一段 C 环境里常见的结构体链表基本语法它兼容 C但还有一些和 C 不同的方便之处。#include iostream using namespace std; // C 的 struct 里可以直接放成员函数 struct Node { int data; Node *next; Node(int val) : data(val), next(nullptr) {} }; int main() { Node *head new Node(0); // 头结点 Node *p head; for (int i 1; i 5; i) { Node *node new Node(i); p-next node; p node; } p head-next; while (p) { cout p-data - ; p p-next; } cout nullptr endl; return 0; }注意 C 里写了构造函数之后new Node(i)就能直接完成“申请内存赋初值”比 C 语言的malloc 手工赋值简洁不少。这里的nullptr是 C11 之后的空指针字面量比NULL更安全不会和整数 0 混淆。很多刷题网站LeetCode牛客等提供的链表模板就是这种 C 风格结构体比如力扣常用的struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };这种带三个重载构造函数的写法本质上就是为了让你写代码时能一行创建节点、灵活接链。你如果看ListNode* node new ListNode(5);不慌看ListNode* node new ListNode(5, head-next);也能马上反应出来它是“创建值为5的节点并让它指向 head 的下一个节点”说明你对构造函数的理解就到位了。我个人在实际操作中的体会是链表这个主题在数据结构的整个体系里就是地基级别的东西。很多人学树、图觉得难回头发现是因为链表没吃透尤其是“节点之间通过引用互相勾连”这个思维模型没建立。把这个模型啃下来后面的二叉树、邻接表、哈希链法、图中的邻接链表全部都是同一个套路的延伸组合。写博客整理这次内容时我又重新把 C 和 Python 两种实现各跑了一遍查漏补缺了两处容易混淆的细节一处是 C 的删除边界条件里前驱为空的情况另一处是 Python 逆序返回prev而不是curr。这些细节看起来微小但考试和面试就喜欢在这种地方设卡。建议你也要亲手把代码跑起来、打印地址和None链看一眼别光看文章看十遍不如自己把输出调整对一遍。
链表从C到Python：插入、删除、逆序与调试避坑指南
开头先交代一个背景我辅导过不少学生的数据结构实验发现链表这一章几乎每个人都会卡一次。不是说它有多难而是链表的操作天然依赖“指针/引用”这种间接跳转的思维方式和数组那种“按下标直取”的直觉完全相反。你翻开课本看代码似乎每行都认识合上书自己写单链表插入十个里有七个会写错前驱指针的衔接。这篇内容我按自己实际讲课和调试的经验来写把链表从结构体定义、遍历、插入、删除、逆序到双链表和循环链表串一遍C语言和Python两种写法都会给出可直接用的代码和踩坑记录。适合正在上数据结构课、准备考研机试、或者刷LeetCode链表题总超时的同学看完至少能解决“代码跑不通”和“懂了但写不对”这两类问题。1. 链表的本质为什么数组已经够用还要造一个它先搞清楚一个最底层的问题链表到底在链什么。数组的逻辑是“连续的盒子”你声明一个int a[10]编译器就给你划拉一块连续内存下标就是盒子的编号。访问a[3]本质是a的起始地址 3 * sizeof(int)一次加减就能算出位置所以数组随机访问是O(1)。代价是什么中间插入一个元素需要把后面所有元素往后挪时间复杂度O(n)而且数组长度是固定的想扩容得重新开辟一整块更大的内存再复制过去。链表走的是另一条路彻底不保证内存连续每个节点单独申请然后用指针把自己和下一个节点串起来。就好比火车车厢车厢之间靠挂钩连接车厢本身停在哪个轨道并不重要只要挂钩不脱整趟车就能跑。你要在中间加一节车厢只需要把前后两节车厢的挂钩解开再重新挂上后面的车厢完全不需要挪位置。这就是链表插入删除快的本质原因——修改几个指针字段时间复杂度O(1)。查找则要从头到尾顺着挂钩一个个走没法跳跃O(n)。我来补一个非常关键的概念区别“不带头结点”和“带头结点”这两种形式几乎是初学者第一道坎。不带头结点的链表头指针直接指向第一个数据节点。一开始链表为空时头指针是NULL。插入到第一个位置时你修改的是头指针本身而不是某个节点的next字段所以函数里经常要传二级指针struct Node **head或者靠返回值来更新头指针。带头结点的链表额外分配一个不存有效数据的节点作为头结点让它的next指向真正意义上的第一个数据节点。哪怕链表为空头结点也始终存在头指针始终非空。这样一来插入和删除第一位的逻辑和插入删除中间位置完全统一不需要单独特判。我的建议非常明确写C语言的单链表时默认都带头结点除非题目明确说“不带头结点”。不是说不带头结点不好而是带头结点能把边界条件从三个降成一个。这会直接决定你调试时流的泪多还是少。2. C语言单链表从结构体到基本操作2.1 结构体定义先想清楚节点里要装什么C语言定义链表节点用的是结构体这是整个链表实验的基础。很多同学上来就写结果连节点的字段都没想清楚一个节点至少包含两部分一个是数据域就是你真正要存的东西可以是整数、字符甚至另一个结构体另一个是指针域存的是下一个节点的地址类型必须是“指向本结构体的指针”。typedef struct Node { int data; // 数据域先拿最简单的int练手 struct Node *next; // 指针域指向下一个同类型节点 } Node;这里有个比较隐蔽的语法点在结构体内部声明next指针时由于typedef还没有生效必须写全struct Node *next。等typedef结束之后你才能用Node这个别名去声明变量、参数和返回值。很多C语言初学者会在这个地方报错然后一脸茫然其实记住一句口诀就好结构体内部引用自己只能用结构体本身的原始名字。如果你要做“在指定位置插入建立单链表”的实验通常还会扩展成“带头结点的尾插法”和“带头结点的头插法”两种建立方式。它们唯一的区别就是新节点接在链表的哪个位置。2.2 带头结点单链表的插入重在找前驱插入操作是单链表里首要的操作也是理解整张链表的钥匙。先给一段完整的、用尾插法建立带头结点单链表的代码#include stdio.h #include stdlib.h Node *createList() { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; return head; } Node *getLast(Node *head) { Node *p head; while (p-next ! NULL) { p p-next; } return p; } void insertTail(Node *head, int value) { Node *last getLast(head); Node *newNode (Node *)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; last-next newNode; }注意到没有尾插法每次都要遍历到最后一个节点所以建立一个n个节点的链表时间复杂度是O(n²)。如果要高效地建立链表应该额外用一个tail指针记录链尾每插入一个节点直接更新尾指针这样建表时间降到O(n)。这是我反复强调的一个点——很多实验报告只要求“能跑通”但面试和机试考的是“时间复杂度是否最优”。在指定位置插入我把关键逻辑抽出来说。假设要在第i个位置插入值为value的节点你需要做的事是从head出发移动i-1次让指针p指向第i-1个节点也就是新节点的前驱。申请新节点newNode把value放进去。让newNode-next p-next这句话把新节点挂在“前驱原本的下一个节点”前面。让p-next newNode前驱的next改为指向新节点。代码是int insertAt(Node *head, int pos, int value) { Node *p head; int i 0; while (p ! NULL i pos - 1) { p p-next; i; } if (p NULL) { printf(position invalid\n); return -1; } Node *node (Node *)malloc(sizeof(Node)); node-data value; node-next p-next; p-next node; return 0; }这个代码有两处初学者最容易写反一是忘了把p移动到前驱直接从头节点开始判断二是在第3步和第4步里把两句的顺序写反。这里我要重点强调node-next p-next必须写在p-next node之前。如果先执行后者前驱的next已经被改成新节点了原本的下一个节点地址就丢了后面再想接就接不上链表直接断裂。这类错误用一句话概括就是牵扯到两个指针修改时先保存要修改的旧值再赋新值。2.3 删除操作的三种边界删头、删尾、删中间删除操作的核心思路和插入一样也是找前驱。但要格外小心三种边界情况。int deleteNode(Node *head, int value) { Node *p head; while (p-next ! NULL p-next-data ! value) { p p-next; } if (p-next NULL) { return -1; // 没找到 } Node *target p-next; p-next target-next; free(target); return 0; }这段代码删除的是第一个值为value的节点。它的巧妙之处在于全程记录的是“目标节点的前驱”这比记录“目标节点”本身要方便得多因为单向链表回不到前面去。删除时让前驱的next绕过目标节点指向目标节点的后继然后free掉目标节点。我见过很多漏掉free(target)的同学实验代码跑完内存泄漏一大片。C语言不像Java/Python有垃圾回收你malloc出来的节点不释放这块内存在程序结束前永远占用。链表实验的体量小可能看不出问题但养成这个坏习惯进真实项目内存泄漏会变成线上事故。删节点必须配套free就像借了钱必须还。删除头部节点时因为有头结点存在头结点本身不能删删的是头结点后面的第一个节点。这个时候p headtarget head-next逻辑和上述代码完全一样不需要特判。这是带头结点方案最大的好处你可以体会一下如果是不带头结点删第一个节点时头指针要更新函数参数得用二级指针代码的复杂度立刻升一个级别。2.4 遍历、清空和逆置三个看似简单实则考人的操作链表遍历是最好写的一个循环走到底void traverse(Node *head) { Node *p head-next; // 跳过带头结点的空头 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这里有个细节带头结点的链表遍历从head-next开始不带头结点的遍历从head开始。上课实验时经常有同学把头结点也打印出来数据里多出一个随机初始化的值排查半天才发现是这个原因。清空链表不少人以为把head-next NULL就完事了。大错特错。你只是把链表的入口封了但链表上每一个节点的内存都还在全部泄漏。正确的清空是逐个释放void clearList(Node *head) { Node *p head-next; while (p ! NULL) { Node *temp p; p p-next; free(temp); } head-next NULL; }注意这个循环里必须先让p跳到下一个节点再去free当前的temp。顺序反过来就出大事free(p)之后p-next已经是无意义的值你再拿它去跳转轻则拿到脏数据重则野指针崩溃。这里的经验是要释放的节点和要继续前进的指针必须分开两个变量。逆置链表也就是常说的单链表逆序。面试和机试几乎必考我给你讲两种写法。一种是迭代法三指针顺序翻转。思路是逐个把指针掉头让每个节点都指向自己的前驱头结点最终指向原来的尾节点void reverseList(Node *head) { Node *prev NULL; Node *curr head-next; while (curr ! NULL) { Node *next curr-next; curr-next prev; prev curr; curr next; } head-next prev; }这个代码的核心是Node *next curr-next;必须先保存后驱。你翻转curr-next之后原来的后驱就找不到了所以要在翻转之前就把下一步的地址锁住。这里叫“三指针法”变量的作用分别是curr是当前要翻转的节点prev是翻转后应该指向的新邻居next是锁住的下一个要处理的节点。另一种是递归法很多人觉得递归清奇但我建议考试时谨慎使用因为递归深度就是链表长度链表长几万条时会爆栈。我一般跟学生说面试写逆序优先三指针迭代考场上最稳。Python 版逆序我们在后面讲因为 Python 的写法完全不同没有指针概念用的是链式引用的重绑定。3. Python单链表的逆序实现与面向对象封装3.1 类结构定义Python 没有指针但类对象的引用天然就是“指向”这让你可以用更直观的方式复刻链表。一个节点class Node: def __init__(self, data): self.data data self.next None一个链表class LinkedList: def __init__(self): self.head None def append(self, data): if self.head is None: self.head Node(data) return p self.head while p.next is not None: p p.next p.next Node(data)注意这里self.head None对应的是不带头结点的单链表。Python 这门语言风格偏向简洁和“显式优于隐式”在数据结构实训里用不带头结点的写法更常见。这也是和前面 C 语言示例刻意区分开来的原因让你两个方向都能驾驭。Python 链表的好处是调试直观你可以在Node类里重写__repr__直接把整条链的列表形式打印出来肉眼检查而不是像 C 语言那样只能 printf 一个字段。class Node: def __init__(self, data): self.data data self.next None def __repr__(self): return fNode({self.data}) - {self.next!r} if self.next else fNode({self.data}) - None3.2 Python单链表逆序三指针法重写Python 的逆序和 C 语言本质同构只是变量名和语法换成 Python 风格def reverse_linked_list(head): prev None curr head while curr is not None: next_node curr.next curr.next prev prev curr curr next_node return prev这个函数和前面 C 语言的reverseList逻辑完全一致但有个区别值得注意Python 不带头结点所以返回的新头就是原来的尾节点。调用时new_head reverse_linked_list(llist.head) llist.head new_head实际操作中很多同学会写错一个点返回的是prev而不是curr。当循环结束时curr已经变成None链表的新头恰恰是prev也就是原来的尾节点。如果你返回curr得到的永远是空指针/空引用。这个坑我见过太多次了。如果你需要看到逆序后打印的效果可以加一个便利方法把链表转成 Python 列表def to_list(head): result [] p head while p is not None: result.append(p.data) p p.next return result3.3 Python递归逆序给思考加一个快照递归逆序虽然性能不是最好的但理解它有助于你真正消化链表结构。看这段def reverse_recursive(node): if node is None or node.next is None: return node new_head reverse_recursive(node.next) node.next.next node node.next None return new_head核心语句是node.next.next node。这句话的意思是让下一个节点的指针反过来指向当前节点。你从后往前想递归不断走到链表尾部把尾节点变成new_head然后一层层往外拔每拔一层就把经过的节点的指针反向。等到最开始那个head的next被置为None整个链表就翻了个个。举一个具体例子链表1 - 2 - 3。递归到3时返回3本身。回到2这一层执行node.next.next node也就是3.next 2再执行node.next None也就是2.next None。链表变成1 - 2 - 3然后回到1这一层执行2.next 11.next None最终3 - 2 - 1。看逆序完成。Python 逆序在 LeetCode 上还有两种特色写法一种是收集值再重建节点def reverse(self, head): vals [] while head: vals.append(head.val) head head.next dummy ListNode(0) p dummy for v in vals[::-1]: p.next ListNode(v) p p.next return dummy.next这个写法虽然空间复杂度是O(n)不如三指针法的O(1)但理解门槛低。面试时候如果时间紧、脑子乱先写出这个能跑的版本再优化成三指针比卡住不动强得多。能跑通再优化是缓解机试紧张的策略之一。4. 循环单链表和双链表两个高频变化体4.1 循环单链表尾指针为何是点睛之笔循环单链表的定义很简单最后一个节点的next不再指向NULL而是回头指向第一个节点带头结点则指向头结点。它的价值在于从任意一个节点出发都能访问到全部节点尤其适合表达周期性结构。最经典的实验是约瑟夫问题n 个人围成一圈报数到 m 的人出列下一人从1重新报数直到只剩一人。这个场景天然是循环单链表。这里要重点讲一个设计细节用尾指针tail代替头指针head来管理循环链表会让代码更顺。为什么因为循环链表里最后一个节点的next正好指向头结点你拿到尾指针tail-next就是头结点头尾都能在O(1)时间访问到。这相当于尾指针顺便包含了头指针的信息。而只有头指针时找到尾节点需要绕一圈O(n)。对比一下约瑟夫的出列操作频繁发生在“当前节点的当前位置”附近直接从头找会慢得多。// 创建n个节点的循环单链表返回尾指针 Node *createCircle(int n) { Node *head (Node *)malloc(sizeof(Node)); head-next head; // 空循环链表自己绕自己 Node *tail head; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data i; node-next tail-next; tail-next node; tail node; } return tail; }约瑟夫出列逻辑void josephus(Node *tail, int m) { Node *p tail; while (p-next ! p) { // 只剩一个节点时p-next p for (int i 1; i m; i) { p p-next; } Node *out p-next; p-next out-next; printf(out: %d\n, out-data); free(out); } printf(leader: %d\n, p-data); }这个代码里p始终指向出列节点的前驱。你从尾指针出发报数m-1次p就到达出列节点前一个节点然后和普通删除一样处理即可。注意这里的p是“绕着圈走”的循环链表的好处就体现在这里。4.2 双链表向前和向后空间换时间双链表每个节点增加了一个prev指针指向前驱。好处显而易见从尾巴往回走不再需要遍历一整条链O(1) 拿到前驱。删除操作也更加自由——你只需要拿到目标节点本身就能通过target-prev和target-next完成线条的重新绑定不需要像单链表那样必须找前驱。C语言双链表节点定义typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;双链表删除target节点void deleteDNode(DNode *target) { if (target-prev ! NULL) { target-prev-next target-next; } if (target-next ! NULL) { target-next-prev target-prev; } free(target); }这是双链表让人舒服的地方传入一个节点就可以完成删除无需从头找前驱。对比单链表必须从头扫一遍找前驱双链表删除是O(1) vs 单链表O(n)。代价是每个节点多一个指针域内存占用多约一半忽略数据域差异时。这个“空间换时间”是数据结构的通用权衡你以后遇到任何设计都要主动想一想多存一份什么信息能让哪个操作更快Python 双链表节点可以这样写class DNode: def __init__(self, data): self.data data self.prev None self.next None双链表在做“LRU缓存”这类需要频繁访问头部和尾部的场景中很有用LeetCode 146 就是经典例子。如果你做完链表实验想进阶可以做一下 LRU把双链表加上哈希表那种“节点O(1)找到并删除”的手感会让你对双链表的理解上一个台阶。5. 链表常见调试方法、典型错误与自学建议5.1 调试手段可视化是唯一的捷径我给学生辅导时反复强调链表调试靠眼睛看打印出来的“箭头链”不靠冥想。你可以写一个辅助函数把链表打成1 - 2 - 3 - None这样的字符串每步操作后都打印一遍。这就相当于给自己装了一台显微镜哪一步接错了一眼就能看出来。Python 里可以直接在LinkedList类中增加def display(self): p self.head nodes [] while p: nodes.append(str(p.data)) p p.next print( - .join(nodes) - None)C 语言里就写一个printList函数把每个节点地址也顺手打印出来void printListWithAddr(Node *head) { Node *p head-next; while (p ! NULL) { printf([%p] %d - , p, p-data); p p-next; } printf(NULL\n); }顺带一提加%p打地址在排查循环链表有没有成环时非常好用。你会发现某些节点地址重复出现那就是循环了自己或者逆序后产生了环。5.2 高频错误清单每个都是血泪史我总结了链表实操中的高频错误按出现频率排序错误类型现象原因修复办法插入时顺序颠倒链表断成两截丢失后半段p-next node执行在node-next p-next之前先捆绑新节点的后手再解开旧连接删除后未free内存泄漏只改指针不释放节点保存目标指针后跳链接再free遍历不使用临时指针直接拿head遍历导致头指针丢失以为指针是值复制始终用局部p移动不动head边界条件漏判空链表崩溃p-next访问了空指针循环条件写p p-next善用短路口诀逆序后丢节点只翻转一半没有保存next三指针法的第一步永远是保存后驱循环链表退出条件错误死循环拿p-next ! NULL判断循环链循环链用p-next ! head判断举个例子展开第一类错误。假设已有A - B要在 A 后插入 X。正确做法是X-next B然后A-next X。如果你反过来先做A-next X那么 A 和 B 之间的连接就断了X-next又不知道去哪里找 B链表就只剩A - XB 被丢在内存里变成孤岛。这种错误单靠人眼盯代码很难看出来但打印过地址后立刻能发现 B 的地址没有出现在从 A 出发的链条上。5.3 从实验到面试的学习路线建议如果你现在还在上课做实验我建议按这个顺序练先用 C 写带头结点的单链表实现插入、删除、查找、遍历、清空。不要求一次写对但要求能在出错后靠打印地址自己找出问题。把同样的操作用不带头结点的方式再写一遍。体会两种形式的差异重点是带不带二级指针。写逆置迭代法和递归法各一遍然后把约瑟夫问题用循环链表做一遍。用 Python 把上述操作全部重写一遍体会语言风格不同但逻辑同构。如果还有精力去 LeetCode 刷 10 道链表题206反转、21合并、141环形、83去重、876中点、19删倒数第n、24两两交换、160相交、148排序、2两数相加。实战中还有个经验值得分享链表题在面试时要先画图再写码。画图不需要多漂亮把节点画成方框、指针画成箭头用不同颜色标出哪根要改、哪根需要先保存。大多数链表 bug 都能在画图阶段发现根本不用等运行时报错。这个习惯我练了几年几乎成条件反射写的代码一次通过率提高了一大截。6. 最后补一个锦囊C 结构体链表的基本语法落到实处很多学校的数据结构实验用 C 写但用的其实是 C 风格的struct 指针。我给你补一段 C 环境里常见的结构体链表基本语法它兼容 C但还有一些和 C 不同的方便之处。#include iostream using namespace std; // C 的 struct 里可以直接放成员函数 struct Node { int data; Node *next; Node(int val) : data(val), next(nullptr) {} }; int main() { Node *head new Node(0); // 头结点 Node *p head; for (int i 1; i 5; i) { Node *node new Node(i); p-next node; p node; } p head-next; while (p) { cout p-data - ; p p-next; } cout nullptr endl; return 0; }注意 C 里写了构造函数之后new Node(i)就能直接完成“申请内存赋初值”比 C 语言的malloc 手工赋值简洁不少。这里的nullptr是 C11 之后的空指针字面量比NULL更安全不会和整数 0 混淆。很多刷题网站LeetCode牛客等提供的链表模板就是这种 C 风格结构体比如力扣常用的struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };这种带三个重载构造函数的写法本质上就是为了让你写代码时能一行创建节点、灵活接链。你如果看ListNode* node new ListNode(5);不慌看ListNode* node new ListNode(5, head-next);也能马上反应出来它是“创建值为5的节点并让它指向 head 的下一个节点”说明你对构造函数的理解就到位了。我个人在实际操作中的体会是链表这个主题在数据结构的整个体系里就是地基级别的东西。很多人学树、图觉得难回头发现是因为链表没吃透尤其是“节点之间通过引用互相勾连”这个思维模型没建立。把这个模型啃下来后面的二叉树、邻接表、哈希链法、图中的邻接链表全部都是同一个套路的延伸组合。写博客整理这次内容时我又重新把 C 和 Python 两种实现各跑了一遍查漏补缺了两处容易混淆的细节一处是 C 的删除边界条件里前驱为空的情况另一处是 Python 逆序返回prev而不是curr。这些细节看起来微小但考试和面试就喜欢在这种地方设卡。建议你也要亲手把代码跑起来、打印地址和None链看一眼别光看文章看十遍不如自己把输出调整对一遍。
