线性表讲到链表这一层算是数据结构里第一道真正意义上的坎。很多人在 part 1 已经把单链表的结点骨架和头插法建表跑通了但一到指定位置插入、链表逆置、带头结点与不带头结点的切换或者从 C 语言换到 Python 重新实现一遍就发现代码开始各种崩。这次 part 2 就把这些操作从原理到代码逐项拆开把链表里高频的考点和应用方式都聊透包括插入、遍历、清空、逆序、双链表、循环单链表以及 C/C/Python 三种语言的表达差异。适合正在学数据结构的学生、准备期末或面试的朋友也适合想彻底理解链表而不是靠背代码过关的人。1. 先理清结点视角链表所有操作的本质都是改指针1.1 为什么链表操作特别容易绕顺序表之所以好理解是因为它像一列按编号排列的储物柜。你知道 0 号柜子紧挨着 1 号柜子找第 k 个柜子只需要算出它的地址一步就走到了。链表完全不是这个思路每个结点散落在内存各处唯一能告诉你下一个结点在哪的就是当前结点里存的指针。换句话说链表没有下标这个概念只有当前位置和下一个位置。这就导致了一个很反直觉的结果你想操作链表的第 3 个结点不能直接跳到第 3 个结点必须从头开始依次经过第 1 个、第 2 个才能摸到第 3 个。所以链表的遍历、查找天然是 O(n)而顺序表是 O(1)。很多人写链表代码容易晕不是数学不好而是没有把结点视角建立起来——你在代码里维护的不是数组的某个位置而是一个不断移动的指针。我自己的经验是拿火车车厢来类比。机车跑在最前面想在第 3 节车厢后面加一节新车厢你得先把机车从第 1 节走到第 3 节想拆掉第 2 节你也得先走到第 2 节。链表操作本质上就是走到目标位置然后改挂钩。插入和删除看着代码只有两三行真正难的是每一步都要清楚手上拿着的是哪个结点、它的指针域还剩多大价值。1.2 三种语言的最小结点定义先把最基础的结点结构摆出来后面所有代码都基于这个定义。C 语言里习惯用结构体加 typedeftypedef struct Node { int data; struct Node *next; } Node;这里有个小坑在结构体内部Node这个别名还没定义完指针域必须写struct Node *next不能写成Node *next。C 环境下可以直接省掉typedef结构体名本身就是类型名struct Node { int data; Node *next; // C 结构体里还能写构造函数 Node(int val) : data(val), next(nullptr) {} };创建结点时 C 用mallocC 用new本质都是申请一块内存并返回起始地址。到了 Python没有指针语法但每个对象变量本质上是引用写起来更接近面向对象的指针class Node: def __init__(self, val0, nextNone): self.val val self.next next三种语言表达同一件事但很多初学者会分别在三个语言里栽一遍C 里忘了给指针分配内存C 里忘了new只声明了一个空指针Python 里误把next None当成下一个结点自己会跑出来。记住一条底层原则结点之间的关联靠的是保存下一个结点的地址而不是靠数组物理上挨着。2. 指定位置插入与建立单链表指针顺序是这里的命门2.1 头插法、尾插法建立单链表两个基础姿势指定位置插入建立单链表是实训题里最常见的说法但实际做实验时建表通常有两种固定姿势。头插法每次都把新结点插到头结点之后代码最短但读入的顺序和最终链表顺序正好相反。尾插法则需要一个额外的尾指针边读边往尾部挂。头插法核心就两行s-next head-next; head-next s;尾插法核心是这样Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next NULL; tail-next s; tail s;对比一下就能发现头插法不需要维护尾指针因为头结点永远是固定的尾插法能保持输入顺序但每插入一个结点都要更新 tail。实训题里如果要求按输入顺序输出链表就该用尾插法如果不要求头插法写起来更省事。2.2 在指定位置插入的指针操作为什么次序不能乱真正让新手头疼的是往链表中间指定位置插入新结点。假设链表带头结点需要往第 i 个位置插入值为 x 的结点意味着要找到第 i-1 个结点把新结点挂它后面。经典代码这样写int insertList(Node *head, int i, int x) { Node *p head; for (int k 0; k i - 1 p ! NULL; k) { p p-next; } if (p NULL) { return 0; // 位置越界 } Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next p-next; // 第一步新结点先指向原后继 p-next s; // 第二步前驱再指向新结点 return 1; }这里最关键的就是s-next p-next;必须写在p-next s;前面。如果先把p-next改成指向 s那么原来的第 i 个结点就丢了s 不知道该指向谁。用一个生活化的说法你要在两节车厢中间插一节新车厢必须先把新车的挂钩挂到后一节车厢上再把前车的挂钩挂到新车上。顺序反了后一节车厢就脱钩了。我自己带学生实验时见过最多的问题不是忘记分配内存而是把这两行写反。写反之后程序通常不会立刻崩但遍历链表时会发现后半段链表神秘消失这种 bug 最难查。建议大家初学时每次写完插入都在纸上画一遍头结点、第 i-1 个结点、第 i 个结点、新结点四个圆圈四个箭头走两轮指针变化。2.3 插入操作在实训题里的三种考察角度实训题里的指定位置插入建立单链表一般会从三个方向出题。第一种只要求按给定的若干个位置和值建表比如依次在第 1、2、5 个位置插入考查的是对找前驱过程的理解。第二种要求从键盘输入时值可能是乱序的要求边读边插成有序表这就需要在每次插入前做一次比较找到第一个比 x 大的结点插到它前面。第三种故意让你处理插到头部和插到尾部这种边界位置看你会不会区分带头结点和不带头结点的差异。第三种其实是很多人的失分点。带头结点时头部插入和中间插入逻辑完全一样因为头结点永远占据第一个位置不带头结点时头部插入要修改头指针本身。这就要引出下面这一节了。3. 带头结点 vs 不带头结点一个哨兵带来的边界差异3.1 带头结点到底规避了哪些坑带头结点指的是在真正的第一个数据结点之前额外放一个不存数据的结点head 指针永远指向它。这个结点在教材里有时叫哨兵结点它最大的价值不是存储而是把链表中没有结点和头指针为空这两种状态彻底分开。带头结点之后空表也是有一个头结点头结点的 next 是 NULL插入和删除代码不用区分是不是第一个位置。因为第一个数据的位置在头结点后面和中间位置的逻辑完全一样。判空也简单head-next NULL。很多工程实践和考研题会特意考不带头结点是因为有些算法题给的头指针直接指向第一个数据结点没有哨兵帮忙兜底。如果读者习惯了带头结点的写法遇到不带头结点的裸链表第一个想到的应该是所有可能改变头指针的操作都需要特殊处理或者干脆让函数返回新的头指针。3.2 不带头结点的正确写法二级指针和返回值二选一在不带头结点的链表里往头部插一个结点如果函数形参只传Node *head那么实参指向的还是旧头结点等于白插。两种常见解法一种是传二级指针void insertAtHead(Node **head, int x) { Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next *head; *head s; }另一种是让函数返回新链表的头指针Node *insertAtHead(Node *head, int x) { Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next head; return s; }我建议在实训代码里统一采用返回值方案。原因很简单二级指针对初学者来说容易在调用处犯糊涂你会总想着head到底传进去了什么返回值方案的调用逻辑更直白head insertAtHead(head, x);一眼就看明白头指针变了。不带头结点时删除第一个结点也同理。删除其余位置只要在函数内部改前驱的 next删除头部就必须让调用方拿到新头。所以很多面试官爱问请在不带头结点的单链表上写删除操作就是看你会不会意识到头指针本身也要跟着动。3.3 循环单链表的判空和遍历终止逻辑循环单链表是带头结点问题的一个延伸。最简单的改造方式尾结点的 next 不再指向 NULL而是指向头结点。这样整个链表首尾相接判空条件从head-next NULL变成head-next head。遍历时也要格外小心。普通链表写while (p ! NULL)循环链表不能这么写因为永远遍历不到 NULL只会死循环。正确写法是记录起始位置绕一圈就停Node *p head-next; while (p ! head) { printf(%d , p-data); p p-next; }循环链表的实际意义在于某些场景需要从任意结点出发都能走回原处。比如约瑟夫问题每次报数到 m 的人出列然后把指针继续往后移如果链表不循环走到尾部就无路可走了。还有人用它做任务轮询、棋盘遍历思路都是一样的把线性结构当成环形跑道。4. 遍历、查找与清空链表基本功里三个容易出错的细节4.1 遍历你写的到底是访问结点还是走到 NULL遍历看起来是所有操作里最没技术含量的实际上翻车率很高。标准模板是Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; }容易犯的错有两个。第一把p p-next;写在访问数据之前导致第一个结点被漏掉最后的 NULL 又被访问一次。第二循环条件写成p-next ! NULL这样最后一个结点永远不会被访问到而且如果链表为空p-next直接就是空指针解引用程序秒崩。我在调试链表遍历时有一个习惯把循环体里第一行改成printf(当前结点地址: %p\n, (void*)p);先看地址输出序列确认指针移动符合预期再去关心 data。这样能把指针移动错了和数据本身错了两类问题区分开。很多同学一上来就打印 data打印出奇怪的值就懵了其实问题往往出在指针上。4.2 查找第 k 个结点下标习惯决定代码长度查找第 k 个结点是单链表基本操作实验里的必考题。这里最大的坑不是算法而是约定k 从 1 开始数还是从 0 开始数教材和考试通常默认第一个数据结点是第 1 个结点。带头结点的链表头结点可以看成第 0 个结点所以找第 k 个结点就是让 p 从头结点出发走 k 步Node *getElement(Node *head, int k) { Node *p head; int count 0; while (p ! NULL count k) { p p-next; count; } // 如果刚好走到第 k 个返回结果否则越界 return (count k) ? p : NULL; }不带头结点的链表就麻烦一些第一个数据结点就是头指针找第 1 个结点应该返回 head 本身。如果你写的是带头结点的代码直接拿去处理不带头结点的链表会凭空多算一个结点。一个常见的面试问法变种是查找链表的中间结点。常规思路是遍历一遍数出总长度再走一遍到中间这是 O(n) 时间里的两次遍历也可以用快慢指针慢指针走一步快指针走两步快指针到尾部时慢指针正好在中点。两者都能过快慢指针写法更聪明一点但前提是你能把边界条件想清楚链表长度为偶数时到底返回前一个中结点还是后一个中结点。4.3 清空链表为什么不能直接置 NULL单链表的清空和销毁经常被混着考。清空是指去掉所有数据结点但保留头结点让链表回到空表状态销毁是连头结点也一起释放。很多初学者直接写head-next NULL这从逻辑上看是空表实际上原来那些结点还残留在内存里成了不可达内存。在 C 语言里这就是内存泄漏程序跑久了或者循环建链多次内存会被一点点吃掉。正确的逐个释放过程核心是释放前先保存后继void clearList(Node *head) { Node *p head-next; while (p ! NULL) { Node *q p-next; // 先记下下一个结点地址 free(p); p q; } head-next NULL; }这里千万不能写成free(p); p p-next;。free(p)之后 p 所指向的内存已经被回收再去读p-next属于悬空指针访问结果是未定义行为。很多编译器不会报错但偶尔运行到某个位置就会段错误。用q先保存后继再 free是链表清理的标准动作。Java、C#、Python 这类带垃圾回收的语言里没有这种烦恼但理解 free 的语义对理解指针生命周期非常重要。5. 双链表与循环单链表单链表的两个常见变形与适用场景5.1 双链表多一根指针换一条回头路单链表最大的短板是只能单向走想到前一个结点只能从头再遍历一遍。双链表在结点里增加一个 prior或 prev指针让每个结点同时知道前驱和后继。结点定义是typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode;插入新结点 s 到 p 之后的完整代码是s-next p-next; if (p-next ! NULL) { p-next-prior s; } s-prior p; p-next s;注意新增的优先级最高的一行是if (p-next ! NULL)。尾结点后面没有任何结点如果不判断就直接访问p-next-prior就是在解引用 NULL直接崩。双链表删除倒是比插入简单p-prior-next p-next; if (p-next ! NULL) { p-next-prior p-prior; } free(p);单链表删除要维护一个 pre 指针跟在前驱后面跑双链表则可以直接从当前结点找到前驱这是它最直观的优势。代价是多存一根指针每个结点多占用 4 或 8 字节但换来的是双向遍历的能力。典型应用场景我能想到三个。第一个是 LRU 缓存需要快速删除最久不用的结点还要把最新访问的结点移动到头部双链表配合哈希表能做到 O(1) 查找、删除、移动。第二个是浏览器前进后退你的历史记录本质上就是一条双向链表上一个页面是 prior下一个页面是 next。第三个是文本编辑器里的撤销栈虽然多数用数组实现但有的实现也用双向链表因为需要频繁在中间插入和删除。5.2 循环链表遍历的终止条件变了游戏规则就变了循环单链表已经在上文提过它的本质是没有尾结点从任何结点出发顺着 next 一直走都能回到出发点。判空条件从head-next NULL变成head-next head遍历终止条件从p ! NULL变成p ! head。在此基础上还能再做循环双链表最后一个结点的 next 指向头结点头结点的 prior 指向最后一个结点。它结合了两者优点从任意结点都能双向绕圈适合做成环形缓冲。面试里循环链表最经典的题是判断链表是否有环。思路是快慢指针快指针每次走两步慢指针每次走一步如果链表成环两者一定会在环里相遇如果没有环快指针一定会先到 NULL。这个题用迭代写很简单但理解它需要先接受循环链表没有 NULL 终点这件事。6. 链表逆序三指针迭代、递归、Python 实现思路殊途同归6.1 三指针迭代法为什么要提前保存后继链表逆序是出镜率最高的链表操作之一也是让很多人第一次体会到指针操作不是想当然的题。最稳妥的迭代法是三指针 prev、cur、nxtNode *reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *nxt cur-next; // 先保存否则改完 next 就找不到后面了 cur-next prev; prev cur; cur nxt; } return prev; }核心就一个cur 要指向 prev但 cur 原来的后继在改完之后就失联了所以必须提前用 nxt 记下来。整个过程可以理解成一边拆一边重接每次把当前结点的箭头反过来然后三个指针整体右移。这个方法对不带头结点的链表适用直接返回 prev 就是反转后的新头。带头结点时稍微有点视觉差异实际处理方式一模一样只要传入的是第一个数据结点反转完返回新头再让头结点的 next 指向这个新头即可。6.2 递归法反转思想更抽象但代码更短递归版的思路是先把 head 之后的所有结点反转好最后再处理 head 和它的后继。可以这样理解假设递归函数已经拿到以 head-next 为头的新链表并且它已经把后半段反转完毕那么 head-next 现在是新链表的最后一个结点我只要让这个结点指向 headhead 指向 NULL就完成了全部反转。Node *reverseList(Node *head) { if (head NULL || head-next NULL) { return head; } Node *newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }写成文字就是三步先反转 head 后面的链让原后继指向 headhead 指向 NULL。递归的难点在于容易绕晕优点是代码短、表达清晰但链表特别长时递归深度会很大可能栈溢出。面试时最好两种写法都准备一般先讲递归思路浅显易懂再补一句如果长度大我会用迭代。6.3 Python 单链表逆序语法不同逻辑完全一样Python 定义链表结点通常用 class反转函数和三指针迭代是一一对应的。唯一的区别是 C 里用Node *nxt cur-nextPython 直接写nxt cur.next引用赋值比 C 的指针看起来温柔但本质一模一样def reverse_list(head): prev None cur head while cur is not None: nxt cur.next cur.next prev prev cur cur nxt return prev很多从 C 转 Python 的人会觉得 Python 链表太简单了因为不用管内存不会有空指针崩溃。但其实 Python 的引用底层就是指针忘了保存后继照样会把链断开只不过不会段错误而是返回一个残缺的链表。调试时用 PyCharm 之类的 IDE 逐步执行看引用的指向变化比在 C 里用 gdb 舒服很多。也正因此我建议先用 C 把链表原理学透再用 Python 验证一次两者互相参照效率最高。6.4 为什么逆序总被拿来当考点逆序题考的从来不是会不会反转而是考察三个能力能不能识别指针的依赖关系、能不能处理空链表和单结点链表、能不能在迭代和递归之间切换视角。这三个能力背后是对链表结点之间靠指针显式关联这个模型的理解程度。顺带提醒一句很多题目要求的逆序是不带头结点的链表然后把它重新接到头结点后面写的时候一定不要漏掉让头结点的 next 指向新头。7. 从结课实验到工程应用链表真正落地时的注意事项7.1 实训题里的单链表基本操作常规套路单链表的基本操作这类实训通常要求实现初始化、插入、删除、查找、遍历、清空、逆置这一整套。我的建议是先别急着堆代码先把每个操作写成一个独立函数main 函数里只做输入读取和菜单调用。很多同学喜欢把所有逻辑堆在 main 里越写越乱最后调试时根本分不清是插入错了还是遍历错了。函数划分可以参考这样一套initList建头结点返回 headcreateListByTail尾插法建表insertList指定位置插入deleteList按位置或按值删除getElement按位置查找locateElement按值查找traverseList遍历输出clearList/destroyList清空 / 销毁每个函数只做一件事出了问题单独调。这是工程里最基本的模块化思想只是很多人到链表实验了还不习惯。7.2 内存、边界、调试踩过的坑都很有共性链表实验里最容易出问题的永远是内存和边界。我建议在每处malloc之后都检查返回指针是否为 NULL虽然绝大多数时候不会失败但这个习惯能帮你挡掉不少潜在问题。第二个边界问题是插入位置越界比如链表有 5 个结点你要插到第 9 个位置必须有个错误提示而不是放任程序乱走。第三个问题是删除不存在的结点、查找不存在的值这些都应该用返回值或退出码表达不要静默失败。调试链表最有效的工具不是打印数据而是打印地址链。在纸上画出当前链表结构然后在关键操作前后分别打印 head 指向哪、每个结点的 next 指向哪。我在培训时经常说一句话链表出 bug十有八九是你以为指针还指在 A实际它已经跑到 B。肉眼追踪几次之后很多问题其实不是代码写得不对是你对程序状态的判断不对。7.3 工程里真正用链表的场景不是每个算法都要链表过来人都知道链表的工程价值取决于场景。存储引擎里的哈希表解决冲突时经常用链地址法每个桶挂着一条单链表图的邻接表用链表数组来表示每个顶点的邻居操作系统管理空闲内存块时也用链表组织空闲分区。这些场景的共同点是元素的个数和顺序动态变化而且需要频繁在中间插入删除。反过来如果是读多写少、需要随机访问数组和下标通常比链表更合适因为 cache 友好、连续内存访问快。最后说一个我自己的学习习惯。每次学完链表的某个操作我都要求自己用 C 写一遍、用 Python 写一遍、再用大白话把这个操作的过程说给同桌听一遍。能说清楚先保存后继再反转的人才是真的懂了链表。这样练上两周后面学树、图、栈和队列的链表实现都会顺很多。