上次讲线性表与链表第一部分的时候我把顺序表和单链表的基础结构梳理了一遍包括节点怎么定义、头指针到底指向什么、最基础的遍历打印怎么写。不少读者看完反馈说结构是看懂了真到自己写插入、删除、逆序的时候还是容易卡壳。这太正常了链表的难点从来不在“看懂结构”而在指针怎么倒腾、边界怎么处理、哪些位置必须判空。所以这篇 part 2 我打算把话题集中在链表的高频操作上包括指定位置插入、清空链表、单链表逆序、循环单链表、双向链表、链表相交再到 C 语言和 Python 两种实现的差异对比最后整理一份实验和实训里最常见的报错与调试点。不管你是正在上数据结构课、准备考研还是刷编程题实训遇到链表题目这篇文章都值得你花半小时认真过一遍。每一段我都会把“为什么这么做”讲清楚而不是丢一段能跑但讲不出道理的代码给你。顺序表时代的“放下标就能取数”的思维惯性到了链表这里必须彻底转换过来否则后面写什么都是懵的。1. 从线性表到链表为什么第二部分要先讲清存储结构1.1 线性表的两条路线顺序存储与链式存储线性表是数据结构里最基础也最重要的逻辑结构它描述的是“一组具有先后关系的数据元素序列”。别小看“先后关系”这五个字它直接决定了你用什么物理方式把数据存下来。常见的是两条路线顺序存储和链式存储。顺序存储就是数组用一段连续的内存空间按顺序摆放元素链式存储就是链表用一组内存地址不一定连续的节点通过指针把它们串起来。很多人学链表容易糊涂根子就在于没分清逻辑结构和物理结构。数组的随机访问很快知道下标 i 就能在 O(1) 时间内取到第 i 个元素代价是插入和删除需要大量移动元素平均时间复杂度 O(n)。链表正好反过来随机访问要沿着指针一路找最坏 O(n)但插入和删除只要找到位置、改改指针就能在 O(1) 时间内完成前提是你已经站在前驱节点上了。这个差异是后面所有算法选择和题目分析的基础。对比项顺序表数组实现链表链式存储随机访问O(1)直达下标O(n)需要遍历插入/删除O(n)要移动大量元素O(1)已知前驱则只改指针空间分配连续内存预分配可能有浪费离散节点天然动态增长扩容需要重新分配整块内存并拷贝申请新节点即可无需整体搬迁你可以把顺序表想象成一排固定间距的货架每件货物有固定编号往中间塞一件新货就得把后面所有货往后挪链表则像一队手拉手的人往中间插一个人只需要让前面那个人松开手、拉住新人新人再拉住后面的人队伍里其他人根本不用动。这个概念想通了后面所有操作都是顺理成章。1.2 带头结点和不带头结点的单链表接着上面的比喻说单链表实现里第一个分岔路就是“头结点到底带不带”。这里必须把两个概念分清头指针head pointer是指向链表第一个节点的指针它可能为空可能指向头结点也可能直接指向第一个数据节点头结点head node则是附加在第一个数据节点之前的一个特殊节点它本身不存有效数据只用来统一操作逻辑。带头结点和不带头结点的区别最典型体现在插入和删除第一个位置节点时代码要不要单独写分支。不带头结点的链表头指针直接指向第一个数据节点。头插时你必须写if (head NULL) { head newNode; } else { newNode-next head; head newNode; }这是两个分支初学的时候很容易漏掉空链表那种情况。删除第一个节点更麻烦你得先保存“head head-next”再把旧头节点 free 掉还得小心链表只有一个节点时 head 变成 NULL后续代码又要不要判空带头结点就省心多了。因为头结点永远存在插入和删除第一个有效节点时统一走“找到头结点操作 head-next”这套逻辑不需要为“空链表”单独写分支。代码变成了newNode-next head-next; head-next newNode;永远是这两行不需要 if-else。这是带头结点最大的收益——操作逻辑统一了边界情况少了一半。代价是多占一个节点内存以及遍历时要记得跳过它。所以我的建议是做实验和考试时除非题目明确写了“不带头结点”否则统一带头结点。它能让你把注意力集中在算法本身而不是反复为边界条件修 bug。2. 单链表核心操作拆解插入、遍历、清空、逆序2.1 指定位置插入先找前驱再改指针“在指定位置插入建立单链表”是实训题里出现频率最高的需求也是理解指针操作的最佳场景。要求“在位置 i 插入新节点”应该怎么写核心思路一句话单链表只有指向后继的指针没有指向前驱的指针所以你无法直接拿到第 i 个节点就插入必须先找到第 i-1 个节点也就是新节点的前驱。找到前驱之后固定操作是两句话新节点先指向后一个节点前驱再指向新节点。顺序不能反。为什么顺序不能反我打个比方。想象一列火车你要在 2 号车厢和 3 号车厢之间加挂一节新车厢。你必须先让新车厢的尾部挂住 3 号车厢再让 2 号车厢挂住新车厢。如果你先把 2 号车厢指向新车厢那 3 号车厢就跟整列火车失去联系了而且你手里已经没有 3 号车厢的“连接信息”了后面再也接不回去。带头结点的情况下一个完整的插入函数长这样int insertList(Node* head, int pos, int val) { Node* p head; int j 0; while (p ! NULL j pos - 1) { p p-next; j; } if (p NULL) { return 0; // 位置非法前驱不存在 } Node* newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { return 0; // 内存分配失败 } newNode-data val; newNode-next p-next; p-next newNode; return 1; }几个关键点要说透。第一j 为什么从 0 开始计数因为带头结点时head 是第 0 个节点第一个数据节点是第 1 个。要在第 pos 个位置插入就得找到第 pos-1 个节点也就是循环走 pos-1 步。第二while 条件为什么要判断 p ! NULL如果 pos 给的太大p 在循环过程中就会变成 NULL再执行 p-next 就是访问空指针程序直接崩溃。养成“访问成员之前先判断指针非空”的习惯能省下后面大量排查段错误的时间。第三插入完要不要判断 newNode 是否为 NULL实验数据量小malloc 几乎不失败但工程环境里内存分配失败是真实存在的多写一行判断就少一个隐患。还有两个边界情况要单独想想在头部插入和尾部插入。头部插入其实就是 pos1循环一步都不走p 就是 head新节点直接接到头结点后面天然符合逻辑。尾部插入时 p 走到最后一个节点如果最后一个节点本身是 NULL说明链表为空此时 pNULL函数会返回 0也就是说你的代码里位置 1 在空表上插入需要单独处理。这正是带头结点的一个好处表头空表这种边界条件已经包含在统一逻辑里了。2.2 链表遍历与清空操作看似简单细节不少遍历是最基础的操作但我在实训里见过不少学生在这个简单环节上翻车原因是遍历过程中“顺便”做了删除或释放操作。当你用 p 遍历链表循环体里如果直接把当前节点 free 掉再执行 p p-next这一步实际上是在访问一块已经还给系统的内存属于典型的野指针访问。一次两次没崩那是因为系统还没把这块内存重新分配出去但它是未定义行为说不准什么时候就出现神秘崩溃。安全的遍历写法是这样void traverse(Node* head) { Node* p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } }如果要一边遍历一边删除正确的思路是先保存下一个节点的指针再处理当前节点。清空链表就是“先保存后释放”的典型场景。清空和销毁还有点区别清空是释放所有数据节点保留头结点让链表回到“空表”可用状态销毁是连头结点也一起释放彻底不用了。void clearList(Node* head) { Node* p head-next; while (p ! NULL) { Node* temp p-next; free(p); p temp; } head-next NULL; }注意最后一行 head-next NULL 一定不能省。很多学生释放完就完了头结点的 next 仍然指向一块已经释放的地址下次再用这个链表时遍历逻辑访问到 head-next 就等于踩到野指针。清空之后链表还存在只是空了头结点的 next 应该置为 NULL这是一个“状态复位”动作。还有一个很多人忽略的点遍历的时间复杂度是 O(n)不管链表多长你想找某个元素就得从头走。所以如果程序里反复出现“查找某个节点的前驱”每次都要从头遍历整体复杂度就会变成 O(n^2)。这种情况下合适的数据结构是双向链表这个我们后面单独讲。2.3 单链表逆序三指针法和递归法单链表逆序是面试题和期末考里出镜率最高的问题之一它考察的就是你对指针操作和迭代过程的理解。核心难点在于把 cur 的 next 指向 prev 之后原来 cur 后面的节点就丢了吗不会前提是你提前用另一个指针保存了它。所以三指针法的本质是“先记后路再改箭头然后集体前移”。三指针法代码如下void reverseList(Node* head) { Node* prev NULL; Node* cur head-next; while (cur ! NULL) { Node* next cur-next; // 1. 先保存下一个节点 cur-next prev; // 2. 反转当前节点的指针 prev cur; // 3. prev 前移 cur next; // 4. cur 前移 } head-next prev; }这四步的顺序一个都不能乱。第 1 步必须放在第 2 步之前否则 cur-next 就先被改掉了你再也拿不到原来的下一个节点。第 3 步和第 4 步是“同步前移”如果把顺序写成 cur 先走、prev 后走那 prev 就永远追不上 cur 了。递归版本写出来很漂亮Node* reverseRecursive(Node* p) { if (p NULL || p-next NULL) { return p; } Node* newHead reverseRecursive(p-next); p-next-next p; p-next NULL; return newHead; }递归的终止条件是“当前节点没有下一个节点”此时它就是逆序后的新头节点。递归回退阶段每次把 p 的下一个节点的 next 指向 p再把自己的 next 置为 NULL。逻辑很优雅但工程上我不推荐递归层数深了容易爆栈链表有十万个节点时基本不可用。面试时两种都要能讲但动手写代码优先三指针——迭代思路更稳也更容易控制。3. 链表进阶形态与经典问题3.1 循环单链表从尾部回到头部循环单链表的特点很简单最后一个节点的 next 不再指向 NULL而是指向头结点带头结点的情况或第一个数据节点。这样从任何一个节点出发沿着 next 走下去都能遍历到全部节点永远不会出现“走到 NULL 无路可走”的情况。约瑟夫问题、时间片轮转调度、循环队列这些场景里循环单链表是天然的数据结构。创建循环单链表时最容易踩的坑是忘记把最后一个节点的 next 指回头结点。学生经常把链接写成普通单链表尾部 next NULL然后遍历的时候用 p ! head 做终止条件结果 p 永远到不了 head死循环了。这种问题排查起来也直接先检查创建链表那一段代码看尾部 next 到底指向哪再确认遍历终止条件跟创建逻辑是一致的。创建带头结点的循环单链表示例Node* createCircularList(int n) { Node* head (Node*)malloc(sizeof(Node)); head-next head; // 空循环链表自己指向自己 Node* tail head; for (int i 1; i n; i) { Node* p (Node*)malloc(sizeof(Node)); p-data i; tail-next p; tail p; } tail-next head; // 关键尾部指回头结点 return head; }遍历循环单链表时终止条件不再是 p NULL而是 p head。这里有个细节如果你用 while 循环先判断再进入循环体第一个节点就可能因为“还没处理就发现 p 指向头结点”而漏掉。所以我常建议遍历循环链表时用 do...while先处理当前节点再移动指针最后判断是否回到头结点。空循环链表的 head-next head 这个状态也要能正确处理不然 do...while 一上来就访问 head 的数据逻辑就乱了。3.2 双向链表插入删除不再需要前驱了双向链表每个节点有两个指针前驱指针和后续指针。为什么需要两个方向因为单链表里删除某个节点你必须知道它的前驱是谁而找前驱通常需要从头遍历一遍。如果链表很长这个开销非常大。有了前驱指针删除节点时通过 p-prior 和 p-next 直接就能操作时间复杂度从 O(n) 降到了 O(1)。双向链表节点定义typedef struct DNode { int data; struct DNode* prior; // 前驱指针 struct DNode* next; // 后继指针 } DNode;插入操作比单链表多几个指针赋值核心原则不变先把新节点和它的前驱后继都连好再修改原有节点的指针。我见过最多的错误是顺序搞反先把 p-next 指向新节点再想给新节点设置 next结果原来的后继节点已经丢了。正确顺序// 在 p 节点之后插入 newNode newNode-prior p; newNode-next p-next; if (p-next ! NULL) { p-next-prior newNode; } p-next newNode;注意中间的 if 判断如果 p 原本是最后一个节点p-next 是 NULL直接执行 p-next-prior 就是空指针访问。这个判断很多人会漏一漏就是崩溃。删除 p 节点本身也一样p-prior-next p-next; if (p-next ! NULL) { p-next-prior p-prior; } free(p);双向链表看起来代码比单链表长但它把遍历找前驱的开销省下来了。如果你的代码里需要频繁“删除当前节点”或者“反向遍历”双向链表是更合适的选择。单链表在这个场景下经常会出现“为了删一个节点先把整个链表走一遍”的低效情况初学者往往意识不到这个问题。3.3 链表相交问题如何找第一个公共节点链表相交二是这个系列里很有代表性的一道题两个链表在某节点之后完全重合如何找到第一个公共节点简单想是双重循环嵌套固定一个链表的节点扫描另一个链表的所有节点时间复杂度 O(m*n)。这个解法能过测试但数据量大一点就会超时面试官也会追问有没有更优方案。标准解法有两种。第一种是双指针法两个指针分别从两个链表头出发一个遍历完自己的链表后跳到另一个链表继续走另一个也同理。因为两个指针走过的路径总长度相等它们一定会在某个节点相遇——要么在交点要么同时走到 NULL。这个思路很巧妙但我个人觉得它不够直观第一次接触时比较难理解为什么两个指针走的路程一定相同。第二种是先统计长度再对齐分别遍历两个链表得到长度 lenA 和 lenB。如果 lenA lenB让 A 链表的指针先走 lenA - lenB 步反之让 B 先走 lenB - lenA 步。两个指针同步前进第一次相等时就是第一个公共节点。第二种方法代码更直白也更好向别人解释。实际写题时如果需要同时比较两个链表是否相交、打印交点数据统计长度的方法还能顺带把两个链表的长度信息输出来用于调试。核心逻辑就是“对齐尾部因为相交之后的部分长度一定相同所以两个链表在各自越过长度差之后剩余长度就一样了再同步走交点必然同时出现”。4. 不同语言实现链表的差异4.1 C 语言结构体链表的基本语法C 语言是学数据结构时的首选语言因为它足够底层指针操作直观能让你亲眼看到内存是怎么被管理的。链表节点定义一般用结构体加自引用指针typedef struct Node { int data; struct Node* next; } Node;很多初学者第一次写 C 链表就被一个语法细节绊倒结构体内部引用自身时不能直接用别名 Node必须写 struct Node。原因是 typedef 的别名在结构体定义完成之前还不存在这是 C 语言语法层面的限制。理解了这个限制就不会再纠结为什么定义里要写 struct Node 了。申请节点内存时规范写法是Node* newNode (Node*)malloc(sizeof(Node));sizeof(Node) 会根据平台自动计算结构体大小避免你在 64 位系统上把指针大小算错。malloc 之后最好立刻初始化newNode-data val; newNode-next NULL;这里的 next NULL 非常重要它保证了新节点的后继是一个明确的“空”状态而不是一块不知道存了什么的内存。很多同学省略了这行后续判断 p-next 是不是 NULL 时就会出问题因为 p-next 是一个随机值。还有一个常见问题当函数需要修改头指针本身时C 语言的传值特性会导致修改无法带出函数。解决方案是传二级指针 Node** head或者让函数返回新的头指针。C 里这个麻烦小一些可以用引用传参 Node* head 解决这也是 C 写链表比 C 舒服的原因之一。4.2 Python 单链表实现类对象和逆序Python 没有指针的概念但对象引用本质上就是指针只是语言替你自动管理了内存不需要手动 free。链表节点定义一般是一个类class Node: def __init__(self, data): self.data data self.next NonePython 实现单链表逆序三指针法的代码逻辑和 C 语言完全一样语法不同而已def reverse_list(head): prev None cur head while cur is not None: next_node cur.next cur.next prev prev cur cur next_node return prevPython 里写逆序容易踩的坑跟 C 语言是一样的保存下一个节点的动作必须发生在修改 cur.next 之前。不一样的是C 语言里错了可能直接段错误Python 里错了往往表现为返回的链表少了一段运行时不报错排查起来更隐晦。所以千万别因为 Python 写起来简单就忽略指针顺序的逻辑这个顺序问题跟语言无关。Python 链表还有一个实操点创建链表时经常用一个“哨兵节点”dummy 来简化头插逻辑。def create_linked_list(values): dummy Node(0) # 哨兵节点不存有效数据 tail dummy for v in values: tail.next Node(v) tail tail.next return dummy.next这个 dummy 节点和 C 语言里的头结点一个思路都是为了让“插入第一个节点”和“插入其他节点”共用同一段代码。Python 里你能更直观地感受到这个设计的好处因为写出来的代码不需要为边界条件分叉。4.3 链表排序的工程实现选择“链表排序”这个需求在实训里也不少见。排序算法通常默认支持随机访问而链表恰恰不支持所以很多在数组上高效的排序算法直接搬到链表上就很别扭。实践中我一般分情况处理链表规模不大比如几百个节点以内最简单可靠的是把链表转成数组用内置排序函数排序后再重建链表。这种做法听起来有点“浪费”但它把时间复杂度做到了 O(n log n)而且代码量最少、不容易出错。工程上先跑通再优化往往是对的。如果题目要求原地排序、不能用数组辅助那就选归并排序。归并排序只需要顺序访问链表天然适合链表结构而且它是稳定排序时间复杂度 O(n log n)空间复杂度 O(1)不考虑递归栈。写法是先找到链表中间节点把链表分成两半递归排序再合并两个有序链表。找链表中点用快慢指针Node* slow head; Node* fast head; while (fast-next ! NULL fast-next-next ! NULL) { slow slow-next; fast fast-next-next; } // 循环结束时 slow 指向中点或偏左中点快指针一次走两步慢指针一次走一步快指针到达尾部时慢指针正好在中点。这个技巧在“链表相交(二)”里也常用到比如判断链表是否有环、找到链表中点本质上都是快慢指针的变体。快排在链表上的实现比较麻烦因为快排依赖随机访问来确定枢纽元素的位置复杂度也不一定优于归并排序所以不是优选方案。5. 常见问题与调试心得5.1 野指针、空指针和内存泄漏数据结构实验课最常出现的错误就是野指针。野指针是指向已释放内存或未初始化内存的指针它最大的危害是“不确定”程序可能这次能跑、下次崩溃可能小数据量正常、大数据量出问题。这类 bug 定位起来最费时间。避免野指针有三个好习惯。第一malloc 之后立刻初始化节点的 next 为 NULL不给野指针留机会。第二free 一个节点之后如果后续还要访问它先把需要的信息保存好。第三访问任何节点成员之前先判断指针是否为 NULL。第三个习惯做不做得到决定了你是一个“能写代码”的人还是一个“会写代码”的人。内存泄漏在 Linux 上可以用 valgrind 检查命令很简单valgrind --leak-checkfull ./your_programvalgrind 会输出哪些内存在程序结束前没有被释放精确到函数和行号。Windows 上可以用 Visual Studio 的 CRT 调试库。如果你不想装这些工具也有个土办法写一个循环创建一万个节点再清空观察内存占用是否回到初始水平。如果内存持续上涨说明某个分支漏了 free满链表的循环里找漏释放的节点效率更高。5.2 实验课和实训题的典型错误根据我带实训的经验学生写链表时最容易犯的错误集中在这几类第一位置计数混乱。带头结点和不带头结点的位置定义不一样带头结点时第 0 个位置是头结点第 1 个位置才是第一个数据节点。很多学生把数组的从 0 开始习惯带过来插入位置永远偏一位。解决方法是先把“第几个节点”和“下标”区分清楚不要在脑子里混用。第二修改指针顺序错误。插入时先把前驱的 next 指向新节点导致原后继节点丢失。这种错误画图就能看出来但很多同学不愿画图靠脑补写代码一错再错。我在课上反复强调的“先接新节点再改原节点”原则考试前一定要默念几遍。第三忘记处理边界条件。插入位置是第一个节点、删除最后一个节点、链表为空这些情况代码里没有对应分支运行时一碰就崩。测试至少准备三组数据空链表、单节点链表、多节点链表基本能覆盖大部分边界问题。第四不带头结点的链表操作忘记更新头指针。因为 C 语言传参是值传递函数内部修改局部变量 head 不会影响外部的 head所以必须传二级指针 Node** head或者让函数返回新的头指针。这个坑很多刚学指针的人都会踩// 错误函数内修改 head外部无感知 void insertAtHead(Node* head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next head; head newNode; // 只是改了本地拷贝 }正确写法是用二级指针void insertAtHead(Node** head, int val) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next *head; *head newNode; }这个知识点如果只在看书时见过、从未手写过考试时基本一定会写错。我建议在练习时把这个场景单独写几遍直到形成条件反射。5.3 调试链表问题的高效方法链表的问题调试和数组很不一样数组是连续的打印整个数组就能看到全貌链表是散落的节点每个节点只能通过指针找到下一个。最有效的调试手段是打印“节点地址 数据 下一个节点地址”printf([%p] %d - %p\n, (void*)p, p-data, (void*)p-next);打印结果里每个节点都显示自己的地址和下一个节点的地址。如果某个节点的 next 是 0x0 但你不希望它结束或者 next 指向一个完全不合理的地址问题就锁定在这里了。这个方法比单步调试快得多特别适合链表这种逻辑连接结构。另一个技巧是“小数据量打印法”。调试时用一个只有三个节点的链表操作后把链表从头到尾打一遍。三个节点的链表结构简单一旦和预期结果不一致立刻能看出是哪步出了问题。很多同学一上来就建一千个节点的链表出了 bug 根本看不清数据分布只会一脸懵。还有一个我要强调的习惯写链表代码时让每个函数只做一件事。插入函数就只处理插入遍历函数就只处理遍历不要在同一个函数里又插入又删除又打印。模块化之后每个函数的边界条件都更清晰bug 的定位范围也小排查自然高效。我个人在实际操作里养成的习惯是任何链表问题都先在纸上画出节点和指针标出“当前节点”“前驱”“后继”三个位置再用笔模拟指针移动确认每一步都保持“后继节点指针没有丢”。画准了再写代码写出来的基本一次通过。这个习惯尤其适合单链表逆序、指定位置插入这种指针操作密集的题目。你可以在实操中也试试先用五分钟画图再动手写代码坚持几周就会发现链表题目不再需要背解法而是顺着逻辑自然就有了。