企业官网建设流程全解析

学链表这件事，几乎每个人都经历过一段痛苦的时期。画图的时候看得明明白白，一到写代码就不断崩溃；自己写的时候以为逻辑对了，一运行却连输出都出不来；好不容易跑通了，改一个删除操作又把整个链表搞丢。作为数据结构里第一个真正意义上的“非连续存储结构”，链表承载的不仅仅是几个结构体和指针，更是一套全新的思维模式——如何用“关系”来组织数据，而不是用“位置”。

这篇心得是我从初学链表到能用它做课程实验、刷算法题、看嵌入式内核代码的一路总结。我会把单链表的基础概念、带头结点与不带头结点的区别、指定位置插入、遍历、清空、逆置，以及循环链表、双链表、嵌入式链表代码、Python和Java实现这些核心内容一起讲透，配合C/C++结构体的代码示例、常见的踩坑经验和调试方法。适合刚学数据结构的学生、准备面试的开发者，以及想在嵌入式场景下用链表管理资源的工程师。先把基础打牢，后面无论遇到什么链表题，你都会有底气。

1. 从数组到链表：先搞清楚为什么要学它

1.1 连续内存与离散内存的本质区别

学链表之前，大多数人接触的第一个数据结构是数组。数组的特点是连续内存：一块整整齐齐、地址连续的空间，每个元素挨着放，通过下标加一个偏移量就能直接定位到任意元素，时间复杂度O(1)。这个特性让数组在“随机访问”场景下几乎无敌。

但数组有一个硬伤：插入和删除代价太大。比如一个长度100的数组，要在第50个位置插入一个元素，后面51个元素全都得往后挪一位。删除同理，前面删一个，后面全部往前补位。这个搬移操作的时间复杂度是O(n)，数据量一大就特别伤。更麻烦的是，数组要求一整块连续内存。一旦系统里内存碎片很多，明明总容量足够，却找不到一块足够大的连续区域来容纳这个数组，程序就只能报错。

链表的存在正是为了解决这两个问题。链表不再要求节点在内存里连续存放，而是每个节点单独散落在任意位置，节点之间通过一个“指向下一个节点地址的指针”串联起来。举个生活化的例子：数组就像电影院里必须连坐在一起的整排座位，买了第5排第10号，那么第9号、第11号一定在旁边；链表就像一个人拉着前一个人的衣角排队，每个人不需要站成一个连续的方块，只要都能抓到前面那个人的衣角，队伍就算成立。

用这样的设计，链表的插入和删除就变成了纯粹的指针操作：只需要改一两个指针，不需要搬动其他任何数据，时间复杂度O(1)。代价是随机访问变差了——想知道第5个节点是什么，必须从第一个节点开始一个接一个往后走，平均要访问n/2个节点，时间复杂度O(n)。数组和链表正好是一对反过来的取舍关系。

我当年第一次听这个课的时候觉得挺简单，后来实际写代码才发现问题全出在“指针到底怎么指”上面。核心的复杂度权衡可以这样列出来对比：

1.2 节点的本质：数据与指针的打包结构

链表的基本单位叫节点（Node）。在C语言里，节点就是一个结构体，里面包含两部分：数据域和指针域。数据域存放实际的数据，比如整数、字符串、结构体对象；指针域存放下一个节点的内存地址。

C语言定义链表节点是这么写的：

struct Node { int data; // 数据域 struct Node *next; // 指针域，指向下一个节点 };

这个定义里最关键的就是struct Node *next。它存储的不是下一个节点本身，而是下一个节点的地址。为什么要存地址而不是直接存节点呢？因为链表节点在内存中是离散的，拿到一个节点的地址，才能通过这个地址跳转到那个节点去取数据。可以把每个节点想象成一个拿着纸条的人，纸条上写着“下一个人的位置在哪里”。你跟着纸条去找下一个人，下一个人又给你下一张纸条，这样就能走完整个队伍。

多个节点通过next指针一环扣一环，就构成了链表。第一个节点被头指针head指向，最后一个节点的next指向NULL，表示“后面没人了”。

1.3 带头结点与不带头结点的区别

这是很多新手第一次写链表就翻车的地方：到底要不要带头结点？这两种写法在教科书、课程实验、面试题里都大量出现，区别和适用场景必须搞清楚。

带头结点的链表，额外分配一个头结点，这个头结点不存放有效数据（data可以随便放），它的唯一职责是作为“哨兵”。头指针head始终指向这个头结点，而头结点的next指向真正的第一个数据节点。即便链表为空，head也不为NULL，只是head->next为NULL。这样做最大的好处是：所有操作（头插、头删、遍历、插入）的代码逻辑完全统一，不需要为“空表”单独写分支。

不带头结点的链表，头指针head直接指向第一个数据节点。链表为空时head直接是NULL。这带来一个问题：在头部插入或删除时，head本身可能会改变，所以代码里必须额外处理“空表”和“首节点特殊对待”的情况。

举个最简单的例子，在链表头部插入一个新节点p。带头结点的写法：

p->next = head->next; head->next = p;

两句搞定，无论链表是否为空都一样。不带头结点的写法：

if (head == NULL) { head = p; p->next = NULL; } else { p->next = head; head = p; }

必须判断head是否为空，漏掉一个分支，空表时就会访问空指针或丢失整个链表。

我的个人建议：课程实验、考试、一般应用代码，优先用带头结点的写法，代码更安全更统一。但如果去看嵌入式内核代码、一些开源项目，不带头结点的写法也很常见，因为它们可以通过二级指针（struct Node **head）优雅地处理头部修改问题。两种写法都要能看懂，至少要会写带头结点的版本。

2. 单链表的基本操作实战：从建表到清空

2.1 C与C++结构体链表的基本语法

C语言和C++定义链表节点在写法上有微妙的差别。C语言里写struct Node，使用时也必须写struct Node *p；C++里可以省略struct关键字，直接用Node *p。C++的结构体还可以带构造函数，初始化起来更方便：

#include <iostream> using namespace std; struct Node { int data; Node* next; // 构造函数，创建节点时直接初始化 Node(int val = 0) : data(val), next(nullptr) {} }; int main() { Node* head = new Node(); // 带头结点 Node* n1 = new Node(10); Node* n2 = new Node(20); head->next = n1; n1->next = n2; cout << head->next->data << endl; // 输出 10 return 0; }

new Node(10)这行代码做了两件事：在堆上分配一块Node大小的内存，调用构造函数把data初始化为10、next初始化为nullptr。为什么必须用new而不是直接用普通变量？因为链表节点需要“活”在函数返回之后，局部变量在函数结束时就销毁了，而new出来的堆内存会一直存在，直到我们手动delete。这是理解链表生命周期的关键。

2.2 在指定位置插入节点的完整逻辑

“在指定位置插入节点”是链表里最经典的基础操作，也是很多实验题的第一步。目标是：在第pos个位置插入一个值为val的新节点。整个操作分三步：

第一步，找到第pos-1个节点，也就是新节点的前驱。因为链表没有下标，不能一步跳过去，只能从头开始顺着next一个节点一个节点数过去。第二步，创建新节点。第三步，修改指针让新节点入链。

关键难点在第三步，修改指针的顺序绝对不能反。正确的顺序是：

newNode->next = p->next; // 先让新节点指向原来的后继 p->next = newNode; // 再让前驱指向新节点

如果先执行p->next = newNode，那么原来的后继节点就会丢失，从p这里往后链就断了，后面那一截永远找不回来。这个顺序问题实在值得强调，我见过太多初学者在这上面卡住。

用插队来类比：队伍里A拉着B的手，新来的C要插到A和B中间。C必须先伸手拉住B（C->next = B），然后A再松开B改拉C（A->next = C）。如果A先把B放了转去拉C，B就跑没影了，队伍直接断成两截。

完整代码（带头结点，位置从1开始计数）：

bool insertNode(Node* head, int pos, int val) { Node* p = head; // 移动pos-1次，找到第pos-1个节点 for (int i = 0; i < pos - 1 && p != nullptr; i++) { p = p->next; } if (p == nullptr) return false; // 位置非法，超出链表长度 Node* newNode = new Node(val); newNode->next = p->next; p->next = newNode; return true; }

这里有个细节：为什么for循环里要判断p != nullptr？因为如果pos大于链表长度加1，比如链表只有3个节点却要在第10位插入，循环会一直往后走直到p变成nullptr，如果不判断就会在下一步访问空指针直接崩溃。判断之后返回false，代表插入失败。

这个函数的边界情况一共有三种：头插（pos等于1）、尾插（pos等于链表长度加1）、中间插入（一般情况）。头插和尾插都统一由同一套逻辑处理，这正是带头结点写法的好处。

2.3 链表遍历：访问每个节点的标准姿势

遍历链表是所有操作的基础，打印、查找、求长度、逆置，全都建立在遍历之上。遍历的核心思想是维护一个“工作指针”，从第一个数据节点开始，每次都做两件事：处理当前节点，然后让工作指针后移。

void printList(Node* head) { Node* p = head->next; // 跳过不存数据的头结点 while (p != nullptr) { cout << p->data << " "; p = p->next; // 后移 } cout << endl; }

这里有一个特别重要的规范：不要移动head指针。head是链表的“根”，一旦把head改成head->next，就再也回不到链表头了，整个链表就找不到了。正确的做法永远是复制一个工作指针p，移动p。这就像你跟一个向导走迷宫，向导手里有一张完整地图，你再拿一张复印版去探索，迷路了大不了回来找向导再复印一张，如果动的原来是唯一那张地图，丢了就彻底完了。

遍历的时间复杂度显然就是O(n)。查找特定值的节点、统计链表中某个值出现的次数，只要在遍历循环里加上判断就行，框架完全一样。

2.4 链表的清空与内存释放

链表用完以后内存怎么办，这是很多人学链表时最后才意识到的问题。C/C++里new出来的节点，如果不清除就永远留在堆上，程序运行时间一长内存越占越多，这就是内存泄漏。清空链表的关键是先保存后继再释放当前节点：

void clearList(Node* head) { Node* p = head->next; while (p != nullptr) { Node* temp = p->next; // 先保存下一个节点地址 delete p; // 再释放当前节点 p = temp; // 移动指针 } head->next = nullptr; // 链表置空 }

为什么必须先保存p->next再delete？因为delete p之后，p指向的那块内存已经被系统收回，里面的next字段已经不可靠了，如果写p = p->next就会读取已经释放的内存，造成未定义行为。正确做法是把后继地址提前装进临时变量temp里，然后拿着temp继续往后走。这个“先备份再释放”的思维，在后续学树、图的删除操作时还会一直用到。

清空和销毁不同。清空（clear）保留头结点，释放所有数据节点，之后链表还能继续插入新节点；销毁（destroy）则连头结点也一起释放，之后head必须置成nullptr否则就成了野指针。有些同学只写了清空没写销毁，程序退出前局部对象析构时又去访问已被释放的节点，就会触发难以排查的运行时错误。

3. 链表的两大经典变体：循环链表与双链表

3.1 循环单链表：从尾巴绕回头

普通单链表最后一个节点的next指向nullptr，表示遍历到此结束。循环单链表做了一个小改动：最后一个节点的next不指向nullptr，而是重新指向头结点（带头结点的情况）或第一个节点（不带头结点的情况），因此整个链表形成一个环。

这个改动带来的最大好处是：从任意一个节点出发，沿着next走下去，一定能遍历到链表里的全部节点。普通单链表就不行，你从中间某个节点出发，走一段就停在nullptr，前面的节点永远到不了。循环链表非常适合那些需要“反复转圈”的场景，比如音频播放器的列表循环、操作系统的进程轮转调度、约瑟夫环问题。

构建循环链表，本质就是在创建完最后一个节点后多做一步：把最后一个节点的next指向头结点：

Node* tail = head; while (tail->next != NULL) { tail = tail->next; } tail->next = head; // 尾巴接回头，形成环

遍历循环链表的终止条件也变了。普通链表判断p == NULL，循环链表得判断p == head，因为p绕一圈回到出发点才算结束。稍微绕一点的地方在于，如果从头结点出发，一开始p就等于head，如果不先走一步直接用while(p != head)会一次循环都不执行。所以通常先让p = head->next，再遍历直到p == head。

约瑟夫环的经典代码就是循环链表的标准练习：n个人围成一圈，从第k个人开始报数，数到m的人出列，然后从下一个人继续，直到剩最后一个人。用不带头结点的循环单链表来实现这个“转圈-删除-再转圈”的过程非常自然，建议每个人都亲自写一遍。

3.2 双向链表：单链表只能向前走的困境

单链表有一个天然的短板：只能从前往后走。想找某个节点的前驱，不好意思，必须从头遍历一遍，时间复杂度O(n)。在实际场景中这很费劲，比如你正在处理链表中间的某个节点，突然想把它的前一个节点找出来做点操作，单链表就尴尬了。

双向链表（双链表）的解决办法是在节点里加一个prev指针，指向前驱节点。节点结构长这样：

struct DNode { int data; struct DNode *prev; // 指向前驱 struct DNode *next; // 指向后继 };

这样每个节点既知道下一个是谁，也知道上一个是谁。双链表插入节点比单链表复杂，因为要改的指针从2条变成了4条。在节点p之后插入新节点newNode，标准步骤是：

newNode->prev = p; // 1. 新节点的前驱指向p newNode->next = p->next; // 2. 新节点的后继指向p原来的后继 if (p->next != NULL) { // 3. 如果p的后继存在 p->next->prev = newNode; // 让后继的前驱指向新节点 } p->next = newNode; // 4. p的后继改为新节点

第3步为什么要加if判断？因为p有可能是最后一个节点，此时p->next为NULL，NULL->prev这种操作会让程序直接崩溃。这是一个很典型的边界条件。

双链表在工程里的应用非常广泛。Java里的java.util.LinkedList底层就是双向链表，C++标准库的std::list也是双向链表。经典的LRU缓存淘汰算法，底层用的就是双向链表加哈希表的组合：哈希表负责O(1)查找，双向链表负责维护数据的新旧顺序。在链表头部插入、尾部删除都是O(1)，而且删除任意一个节点时可以立即找到它的前后节点完成衔接。

3.3 嵌入式场景下的链表代码微言大义

嵌入式系统里链表随处可见：管理定时器、管理任务队列、组织空闲内存块。但嵌入式环境有一个特殊约束：很多场景下不允许动态分配内存。原因有三个：动态内存分配（malloc）可能产生碎片，长期运行的系统会因此越来越难分配到连续内存；分配和释放的时间不确定，实时任务可能因此错过截止时间；单片机上的堆非常小，一不小心就分配失败。

所以嵌入式里更常见的是“静态节点池加侵入式链表”的组合。所谓静态节点池，就是提前用数组定义一批固定数量的节点，用链表把它们串起来管理；所谓侵入式链表，核心思想是：链表的指针不是塞在业务数据结构里面作为普通成员，而是业务结构体“嵌入”一个链表节点结构体，通过这个内嵌的链表节点把整个结构体串起来。

Linux内核里的list_head是最经典的侵入式链表。简化来看是这样的：

struct list_node { struct list_node *next, *prev; }; struct timer_node { int timeout; // 业务数据 struct list_node link; // 内嵌链表节点 };

一个timer_node想要挂到定时器链表上，操作的是link成员；当拿到某个link的地址，如何找到它所在的timer_node？内核用container_of宏，通过结构体内成员的偏移量反向计算出宿主结构体的起始地址。这个过程说白了就是：我知道某个成员在结构体里的偏移量，也知道成员的地址，那么成员地址减去偏移量就是结构体地址。

嵌入式的这种写法好处很明显：业务结构体可以同时内嵌多个list_node，挂到多个不同的链表里。比如同一个任务可以既挂在“就绪链表”里，又挂在“延时等待链表”里，各用各的link成员，互不干扰，也不需要为“一表一字段”设计冗余的指针。这就是为什么你会看到很多嵌入式代码里的链表长得跟教科书完全不一样的原因。

4. 多语言实现对比：C/Python/Java怎么选

4.1 Python单链表逆序的简洁写法

Python语言本身没有内置链表结构，但用类来模拟链表节点很容易，而且Python的引用天然就是指针，不需要考虑内存分配和释放，写起来非常舒服：

class Node: def __init__(self, val=0, next=None): self.val = val self.next = next

Python实现单链表逆序，迭代写法非常简洁：

def reverse_list(head): prev = None cur = head while cur: nxt = cur.next # 保存下一个节点 cur.next = prev # 当前节点的next指向前一个 prev = cur # prev前移 cur = nxt # cur前移 return prev

这段代码的核心逻辑是三个变量在同步漂移：prev是已经逆置好的那一段链表的头，cur是当前待处理的节点，nxt是cur原本的后继。每一步就是把cur的next掰向prev，然后把prev和cur各自向前推一格。

Python写链表的优势是直观、不用管内存，特别适合用来理解算法思想本身；劣势是性能差一些，而且Python递归有默认深度限制（大概1000层），所以递归逆置在Python里受限于链表长度。刷题和教学用Python足够，但你要是写高性能网络服务，还是得回到C或C++。

4.2 Java链表的封装与手写链表面试

Java里平时开发直接用java.util.LinkedList就行，它的底层就是双向链表，同时实现了List和Deque接口，既能当列表又能当栈和队列。但面试和课程作业往往要求手写链表，这时候需要一个最简节点类：

class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }

Java的引用类型和C的指针本质上是同一个概念，只是Java里引用不能做算术运算，不能把一个引用加1变成另一个引用。Java的null就相当于C的NULL。看懂了C的指针，Java链表就是换了一层皮；反过来，先学Java链表再学C指针，也会更容易理解“引用到底是什么”这个抽象概念。

Java有一个需要注意的地方：内存管理交给垃圾回收器（GC），不需要手动delete，但这不代表链表操作就不会出内存问题。删除一个节点时，如果还把节点的next指针指着链表里的其他节点，这个被删除的节点仍然会被后续遍历访问到，形成所谓的“慢内存泄漏”——GC认为它还有人引用所以不回收它。标准的Java链表删除，比如LinkedList的unlink方法，会把被删节点的前后引用全部置null，这是有讲究的。

4.3 语言差异背后的思维转变

同样一个链表逆序，用C、Python、Java写一遍，你会明显感受到不同语言对内存和逻辑的关注点不一样：

这个对比很能说明问题：C系语言写链表时你时刻感知到内存的存在，知道每个节点是new出来的、用完要还回去；Python和Java让你更专注算法逻辑本身，但也容易让你忽略底层开销。我见过很多先学Python再学C的同学，写C链表时经常忘了释放节点，就是因为习惯了垃圾回收。反过来，先学C的同学写Python时，也会不自觉地想去“释放”对象。

我的建议是：链表入门直接用C或C++，因为指针、内存、结构体这些概念是链表的地基，用高级语言学容易把地基一笔带过。等用C把链表的增删改查都写熟了，再回头看Python和Java的链表，会发现思路完全一致，只是语法不同。

5. 实战案例：单链表逆置的三种思路

单链表逆置（也常叫反转链表）是链表里出镜率最高的操作，笔试面试、课程试验、编程题实训全都离不开它。这道题考的不是复杂的算法，而是你对指针关系的掌控能力。同一个需求，至少有三种写法，我一个个讲清楚。

5.1 迭代逆置：三个指针的走位

迭代法也叫三指针法，是工程上最推荐的方式，时间复杂度O(n)，额外空间O(1)。核心思路：准备三个指针prev、cur、nxt，从头到尾走一遍，每到一个节点把它的next指向prev，然后三个指针整体往后平移。

用C语言写是这样：

struct Node* reverseList(struct Node* head) { struct Node* prev = NULL; struct Node* cur = head; while (cur != NULL) { struct Node* nxt = cur->next; // 先保存后继 cur->next = prev; // 掉转方向 prev = cur; // prev前移 cur = nxt; // cur前移 } return prev; // 新的头结点就是原来的尾节点 }

理解这段代码的关键是看到三个指针在同步“漂移”。可以把链表想成一串珠子，你每走到一颗珠子，就把它原来的绳子解下来，绑到前面那颗珠子上。走完一整串，所有珠子的朝向都reverse了，而原来最后一颗变成了新的头。

为什么会丢链？因为当你执行cur->next = prev时，cur原来指向后继的那条线已经被切断了，如果之前没把nxt保存下来，就再也找不到后面那一截了。这和清空链表时“先保存再释放”是同一个思想。

注意这个函数的返回值：原来的head在逆置后变成了尾节点，此时它的next已经是NULL了，真正的新的头节点是原来最后一个节点。所以在调用处要重新接收返回值，不能还拿着旧head不放。常见错误就是有人写reverseList(head)之后继续用head遍历，结果空了，因为head已经变成尾节点了。

5.2 递归逆置：用栈的思维

递归法代码量最少，但理解门槛最高。代码如下：

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的后继节点反过来指向head head->next = NULL; // head变成尾节点 return newHead; }

递归的思维是“先处理后面的，再处理当前的”。假设链表是A->B->C->NULL，调用时先递归处理B->C->NULL，得到已经逆置好的C->B->NULL，newHead指向C。此时回头处理A：A->next是B，而B的next目前指向NULL，执行A->next->next = A后，B->next变成了A，于是C->B->A，然后A->next置NULL，完成整段逆置。

递归的好处是代码优雅，考察你对递归和引用关系的理解；坏处是需要栈空间，栈深度等于链表长度。如果链表有十万个节点，递归就会栈溢出崩溃。所以工程上我推荐迭代法，面试时两种都要能写，因为面试官想通过递归看你是否能“把问题规模缩小”。

5.3 头插法逆置：用现成的头插操作兜底

第三种思路最朴素：新建一个空链表头newHead，然后遍历原链表，每遇到一个节点就用头插法把它插到newHead后面。因为头插法总是把新节点放在最前面，原链表的第一个节点最终会被挤到最后，原链表的最后一个节点反而变成最前面，逆置效果就出来了。

struct Node* reverseByHeadInsert(struct Node* head) { struct Node* newHead = NULL; struct Node* p = head; while (p != NULL) { struct Node* temp = p->next; // 保存后继 p->next = newHead; // 挂到新链表的头部 newHead = p; // 更新新链表头 p = temp; // 继续遍历原链表 } return newHead; }

这种写法空间复杂度其实也是O(1)，因为并没有真的创建新节点，只是把原来链表的节点按头插方式重新排列。它的好处是思路直白，不容易错；坏处是代码在视觉上多了一个新头变量，逻辑上跟迭代法殊途同归。

三种方法做个对比，方便你选择：

5.4 编程题实训中的链表应用

课程实验里光会建链表还不够，通常还会配套几道经典应用题。高频的是这三个：

第一个，两个有序链表合并。思路是用双指针分别遍历两个链表，比较当前节点的值，谁小谁接入结果链表，然后对应指针后移，直到其中一个走完再把另一个剩余部分直接接上。这本质上是归并排序合并过程的链表版本。

第二个，删除链表的倒数第n个节点。比较典型的做法是快慢双指针：快指针先走n步，然后快慢指针同步走，快指针走到尾时慢指针正好停在倒数第n个节点的前驱位置，改指针跳过它即可。这个题考的是对距离差的把握，跟找链表中间节点是同一个套路。

第三个，判断链表是否是回文链表。朴素做法是遍历后存入数组再判断，进阶做法是用快慢指针找到中点，把后半段逆置，再逐节点比较。你会发现这里用到的全都是前面讲过的基本功：遍历、找中点、逆置。

6. 常见问题与调试心得

6.1 空指针崩溃：七成新手的噩梦

我辅助过不少学数据结构的同学，链表代码报错排在第一名的永远是空指针。典型的场景是：遍历循环里没有判断当前指针是否为NULL就直接访问p->data或p->next；插入操作没有考虑空表；删除操作没有保存后继；还有更隐蔽的——传参传的是值，函数内部改了头指针，外面根本不生效。

C语言里要修改头指针本身，必须传二级指针或者返回新的头指针，这一点特别容易踩。比如在不带头结点的链表里写删除首节点：

void deleteFirst(struct Node** head) { if (*head == NULL) return; struct Node* temp = *head; *head = (*head)->next; free(temp); }

这里为什么用struct Node** head而不是struct Node* head？因为*head = (*head)->next这行代码要修改调用方手里的head变量，必须通过二级指针间接修改。如果只传一级指针，函数内部改动不影响外部，删除等于没删。同理，所有需要修改头指针的操作（头插、头删、逆置、销毁）都得注意这个问题。

6.2 内存泄漏与野指针

C/C++的内存问题永远是链表调试的隐形杀手。new和delete、malloc和free必须成对出现，这个纪律不能松。有几类典型问题：忘记delete导致的内存泄漏，程序跑越久内存占用越大；delete之后没有把指针置空，后来又去访问这个指针，读到的内容是随机数据，这就是野指针；释放节点时顺序不对，先释放了当前节点再去访问它的next，直接崩溃。

检测这类问题可以靠工具。Linux环境下用valgrind：

gcc -g -o test test.c valgrind --leak-check=full ./test

valgrind会详细报告哪些内存没释放、哪一行代码读取了非法内存。编译器开启地址消毒器也能提前拦截：

gcc -g -fsanitize=address -o test test.c

地址消毒器跑起来以后，一旦访问越界或使用已释放内存在编译出的程序运行时会立刻报错。我建议初学阶段就养成开这两个工具的习惯，省下无数排查时间。

6.3 调试技巧：画图、打印、断点三板斧

链表调试靠肉眼看代码往往会看到崩溃，我自己的亲身体会是三板斧组合最管用。

第一板斧是画图。写代码之前先画链表，标出每个节点的地址、data、next指向。纸上画清楚了再写代码，错误率下降一多半。等我写熟了，也开始在纸上画了上百张节点图，这一步帮我建立了对指针关系的直觉。

第二板斧是打印。写一个dumpList()辅助函数，把当前链表每个节点的地址、数据、next地址全部打印出来：

void dumpList(struct Node* head) { struct Node* p = head; int index = 0; while (p != NULL) { printf("[%d] addr=%p data=%d next=%p\n", index, p, p->data, p->next); p = p->next; index++; } printf("length=%d\n", index); }

在逆置、插入、删除的每一步之后都调用一次dumpList，你就能看到指针变化的完整过程，问题立刻现形。这个方法比断点调试更快，因为链表操作的错误通常体现在“结构连错”而不是“数值算错”。

第三板斧是断点watch。当你用调试器逐步执行时，把关键的cur和prev变量添加watch，观察它们每一轮的变化是否符合预期。尤其是cur->next被修改的那个瞬间，watch窗口能让你看清楚它从指向后继变成指向前驱的过程是否在正确位置。

我当年遇到过最头疼的问题就是逆置之后打印链表，发现只有第一个节点，或者出现循环打印不停。后来靠着dumpList打印length才发现，原来是最后一步的prev返回错了，导致新的头指针指错了节点；还有一次是忘了把head->next置为NULL，尾节点还指着原来的下一个节点，打印时就掉进了环里。这些问题靠读代码很难一眼找到，打印输出一下就清清楚楚。

我自己现在写链表，已经不需要在纸上画图了，但初学阶段每个操作我都会画，画了不下100多张图。可以这么说，谁先学会“把逻辑画成指针关系”，谁就能最快绕过链表这道坎。链表教给我们的远不止一个数据结构，它让我们第一次真正理解“引用”和“关系”怎样表达数据之间的联系。这个思维带到后面的树、图、数据库索引、操作系统内核，全都会反复用到。如果你也正被链表折磨，别急着刷题，先回到一张纸一支笔，把节点和指针的每一步走位画清楚，再回来看代码，你会发现自己突然就通了。