单链表的建立和逆置是数据结构入门阶段避不开的一组操作。很多人在课堂上听懂了“链表是一串节点通过指针串起来”的概念但真到写代码时还是会卡在两件事上第一怎么把一组数据正确建成链表第二怎么把链表反转回来而不丢节点。这个主题看着基础实际上非常考察对指针、节点和链式结构的理解。如果你正在准备数据结构实验、考研复习或者刚开始用 C 语言写链表代码这篇内容会从建立到逆置完整拆一遍重点讲清楚每一步为什么这么做以及出错时应该往哪里排查。1. 先搞清楚单链表建立的两个核心问题1.1 头插法和尾插法到底差在哪单链表的建立本质上就是不断创建新节点再把新节点挂到已有链表的合适位置上。挂法只有两种挂在头部也就是头插法挂在尾部也就是尾插法。头插法的特点是每次新节点都插在头结点或第一个节点之前。这样做代码很简洁核心逻辑就两行node-next head-next; head-next node;但要注意头插法建立链表后链表中节点的顺序和原始输入顺序是相反的。也就是说你输入的顺序是 1、2、3最终链表从头到尾遍历出来是 3、2、1。原理也很简单因为每个新节点都被压到了最前面后进来的节点永远排在先来节点的前面。尾插法则是维护一个尾指针 tail每次新节点都追加到 tail 的后面然后更新 tail。这种建表方式更符合“按顺序生成链表”的直觉遍历出来的节点顺序和输入顺序一致。代价是需要多维护一个指针并且在插入时多一个 tail 更新的步骤。实际实验里怎么选如果你只是需要生成一个顺序和原始数组一致的链表用尾插法如果你想模拟“反转插入”的效果或者在逆置操作里复用头插法的思路就从头插法入手。两种方法都不难但一定要自己动手写一遍把每一步的指针变化画出来。1.2 带头结点和不带头结点怎么选很多初学者学到链表时会被“头结点”这个概念绕晕。这里要区分两个词头指针和头结点。头指针是指向链表第一个节点的指针变量它本身不是一个节点只是一个保存地址的变量。头结点则是链表中实际存在的一个节点只是这个节点的 data 区域通常不存有效数据只用来作为链表的起点。带不带头结点直接影响代码逻辑。带头结点时头指针 head 永远指向一个固定的头结点即使链表为空head 也不为 NULL。这样在头插、尾插时不需要对 head 本身做修改只需要修改 head-next。很多教材和考试题目默认使用带头结点的写法因为边界条件更好处理。不带头结点时判断链表为空的条件是 head NULL插入删除时如果操作的是第一个节点需要修改头指针本身所以函数往往要接收二级指针 Node** headRef或者在返回时返回新头指针。我自己在做实验时更建议先把带头结点的版本写熟再尝试不带头结点的版本。原因很简单带头结点可以让你把注意力集中在“指针怎么改”上而不是被“头指针要不要更新”干扰。等理解了本质再看两者差异就很轻松了。2. 单链表建立从节点定义到完整可运行代码2.1 节点结构、创建函数和遍历打印不管你用头插法还是尾插法第一步都是定义节点结构。C 语言里最基础的定义长这样#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node;data 存数据next 存下一个节点的地址。这里的 struct Node *next 是一个指向自身结构体类型的指针这种定义方式在链表、树等结构里非常常见。接下来写一个创建节点的辅助函数Node* createNode(int data) { Node* node (Node*)malloc(sizeof(Node)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-next NULL; return node; }每次创建节点都通过这个函数来做能避免重复写 malloc 和初始化代码也能统一处理分配失败的情况。注意别省略 node-next NULL 这一步。新人经常在这里踩坑malloc 出来的内存在堆上里面的值不确定如果不手动把 next 置空后续遍历时可能访问到野指针程序直接崩溃。然后是遍历打印函数void printList(Node* head) { Node* p head; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }如果带头结点打印时要从 head-next 开始否则会把头结点的无效 data 也打出来。这里我给的是通用版本实际使用时要根据你的链表结构调整。2.2 尾插法建立链表尾插法的核心是维护一个 tail 指针让新节点总是接到链表的最后面。写一个用数组创建链表的函数Node* createListByTail(int arr[], int n) { Node* head createNode(0); // 头结点data 不存有效数据 Node* tail head; for (int i 0; i n; i) { Node* node createNode(arr[i]); tail-next node; tail node; } return head; }这段代码的逻辑很直白头结点先充当 tail然后每创建一个节点就把它挂到 tail 后面再把 tail 更新成新节点。循环结束后链表的节点顺序和 arr 的顺序完全一致。实际运行时可以用这样的方式测试int main() { int arr[] {1, 2, 3, 4, 5}; Node* list createListByTail(arr, 5); printList(list-next); // 打印结果是 1 2 3 4 5 return 0; }我建议第一次试验时先不要传长度而是用固定的小数组跑通确认遍历顺序正确后再考虑从控制台输入数据。不要一上来就写一个接收用户输入循环建表的版本那样出了问题很难判断是输入的问题还是链表逻辑的问题。2.3 头插法建立链表头插法的代码更短但理解起来稍微绕一点Node* createListByHead(int arr[], int n) { Node* head createNode(0); for (int i 0; i n; i) { Node* node createNode(arr[i]); node-next head-next; head-next node; } return head; }每一次循环新节点 node 的 next 指向原本的第一个节点 head-next然后 head 的 next 再指向 node。这样新节点就顶替了原来第一个节点的位置成为链表新的第一个有效节点。用 arr {1, 2, 3, 4, 5} 测试时遍历结果是 5 4 3 2 1。这不是 bug而是头插法的固有特点。如果你希望最终顺序和输入一致可以在主函数里倒序遍历数组再头插或者干脆使用尾插法。2.4 两种建表方式的效果差异验证怎么确认你写的建表代码是对的最直接的方法是打印。把同一个数组分别用尾插法和头插法建立成链表然后分别打印int arr[] {1, 2, 3, 4, 5}; Node* listTail createListByTail(arr, 5); Node* listHead createListByHead(arr, 5); printf(尾插法结果: ); printList(listTail-next); printf(头插法结果: ); printList(listHead-next);输出会是这样尾插法结果: 1 2 3 4 5 头插法结果: 5 4 3 2 1如果打印结果符合这个预期说明建表这一步已经通了。如果输出乱序或者中途出现异常值先检查 createNode 里 next 是否初始化再检查插入时指针赋值的前后顺序。头插法里最容易写错的顺序是反过来也就是先执行 head-next node再执行 node-next head-next。这样会导致 node-next 指向 node 自己链表直接变成环打印时就会无限循环或死循环。这个问题在调试时非常典型后面排查部分会再说。3. 单链表逆置三种写法都要会3.1 迭代逆置最常用的基础写法单链表逆置就是让每个节点的 next 从指向后继变成指向前驱。最经典、最推荐掌握的写法是迭代法。以不带头结点的链表为例逆置函数如下Node* reverseList(Node* head) { Node* prev NULL; Node* cur head; while (cur ! NULL) { Node* next cur-next; // 先保存下一个节点 cur-next prev; // 当前节点指向前驱 prev cur; // prev 前进 cur next; // cur 前进 } return prev; // 循环结束时 prev 是原链表的最后一个节点也就是新链表的头 }这段代码的核心在于“先保存再修改”。每次修改 cur-next 之前必须先把它原本指向的下一个节点用临时变量 next 保存下来。如果不保存下一步 cur next 时就没有了依据后面的节点全部丢失这被称为“断链”。三个指针的移动过程可以这样理解prev 始终指向当前节点在新链表中的前驱cur 指向当前待处理节点next 保留 cur 在原链表中的后继。每一步都让 cur 脱离原来的链表反过来指向 prev然后再整体前进一格。这个算法的空间复杂度是 O(1)时间复杂度是 O(n)只需要遍历一次不应该用额外数组或栈来完成逆置。如果你看到有人创建新链表来逆置那也能实现但效率和数据结构本身的“链式”优势就没体现出来。3.2 递归逆置代码最短但要注意栈开销递归解法写出来非常简洁理解起来却需要一点想象力Node* reverseListRecursive(Node* head) { if (head NULL || head-next NULL) { return head; } Node* newHead reverseListRecursive(head-next); head-next-next head; head-next NULL; return newHead; }递归的终止条件是当前节点为空或者当前节点是最后一个节点。当递归到链表的最后一个节点时它会被当作新链表的头结点返回。然后每一层递归在做的事情是让当前节点后面的那个节点重新指向当前节点再把当前节点的 next 置空。举个例子链表是 1 - 2 - 3。递归到最后一层时head 是 33-next 是 NULL所以直接返回 3。回到处理节点 2 的那一层执行 head-next-next head也就是让 3-next 指向 2形成 3 - 2然后执行 head-next NULL断开 2 原来指向 3 的引用。再回到处理节点 1 的那一层执行 2-next 11-next NULL。最终得到 3 - 2 - 1。递归写法的优点是好记缺点也非常明显递归深度等于链表长度链表太长时会占用大量函数调用栈空间极端情况下甚至会导致栈溢出。所以如果是实验课写一个长度 100 以内的链表递归完全没问题如果是在生产环境或算法题里遇到超长链表优先选择迭代法。3.3 头插法逆置借用头结点的快速思路如果你建表时用的是带头结点的方式逆置还可以借用头插法的思想遍历原链表把每个节点从原位置摘下来重新头插到带头结点的链表上。void reverseByHeadInsert(Node* head) { if (head NULL || head-next NULL) { return; } Node* cur head-next; // 指向第一个有效节点 head-next NULL; // 断开原链表 while (cur ! NULL) { Node* next cur-next; cur-next head-next; head-next cur; cur next; } }这个过程非常像是用头插法重新建立一遍链表。原链表每遍历一个节点就把它摘下来插到 head 后面。由于头插法天然会让后插入的节点排到前面所以遍历完整个链表后节点顺序就完全反转过来了。这种写法在带头结点的场景里很直观而且不需要返回新头指针因为 head 始终没有变。考试和实验题里如果明确说了“带头结点的单链表逆置”用这种方法会比较省事。3.4 三种逆置方式对比逆置方式是否有头结点空间复杂度时间复杂度优劣势迭代逆置均可O(1)O(n)推荐优先掌握无额外栈开销递归逆置均可O(n)O(n)代码短但长链表可能栈溢出头插法逆置带头结点更方便O(1)O(n)思路与头插建表统一适合有头结点场景这三种方法不需要追求一次全部吃透可以先从迭代逆置入手把它写得滚瓜烂熟然后再用带头结点的头插法做一遍对比最后有时间再理解递归版本。三个版本都写一遍之后你对“指针如何反转”这个问题的理解会扎实很多。4. 逆置结果怎么验证、错误怎么排查4.1 验证方法和测试用例设计逆置代码写完后怎么判断对不对不要只看程序不报错就认为没问题。最简单可靠的验证方法是逆置前打印一次逆置后再打印一次对比结果是否正好反向。测试用例建议按下面几类准备空链表传入 NULL程序不应该崩溃应该直接返回 NULL。只有一个节点逆置后仍然是这个节点。两个节点例如 1 - 2逆置后是 2 - 1。多个节点且包含重复元素例如 1 - 2 - 2 - 3逆置后是 3 - 2 - 2 - 1。长链表例如 10000 个节点用于观察递归版本是否栈溢出以及迭代版本能否稳定跑完。空链表和单节点这两个边界经常被忽略但恰恰是考试和面试最容易考察的点。如果你写的逆置函数没有针对 head NULL 做保护空链表直接调用时可能发生空指针访问。4.2 断链、空指针和死循环排查逆置代码最常见的三个问题是断链、空指针访问、死循环。断链的现象是逆置后链表变短了部分节点凭空消失。原因几乎都是修改 cur-next 之前没有保存 next。排查时就盯住一点每次修改 next 之前是不是已经用一个临时变量记住了后续节点的地址。空指针访问的现象是程序运行到某一步就崩溃。常见原因是循环条件写错比如 while (cur-next ! NULL) 而不是 while (cur ! NULL)。当 cur 已经变成 NULL 时再去访问 cur-next 就会崩溃。死循环或卡住的现象是程序一直不结束。最常见的原因是链表出现了环典型场景就是头插法建表时指针赋值顺序写反导致某个节点的 next 指向自己。排查方法也很简单在遍历循环里加一个计数器如果循环次数超过链表节点数就说明存在环。更正式的做法是使用快慢指针两个指针一个每次走一步一个每次走两步如果它们相遇说明链表有环。4.3 内存释放和工程规范问题逆置操作本身不涉及新建或删除节点只是修改指针方向所以不需要释放内存也不应该申请新内存。如果你在逆置函数里看到了 malloc就要反问一句这是必要的吗但建表阶段申请的内存在程序结束时需要释放。很多实验课代码不写释放逻辑也能运行因为程序退出后操作系统会回收进程的堆内存。但在一个长期运行的程序或一个频繁建表、逆置的程序里不释放内存会导致内存泄漏。释放链表需要一个一个节点释放不能只释放头结点void freeList(Node* head) { Node* cur head; while (cur ! NULL) { Node* next cur-next; free(cur); cur next; } }另外逆置操作如果涉及带头结点和不带头结点的混用一定要在函数注释或命名里写清楚。我见过不少同学把带头结点的链表传给不带头结点的逆置函数结果发现头结点也被反转进了链表里打印结果多了一个奇怪的 0 或者垃圾值。这不是算法错而是接口约定没对齐。5. 从建表和逆置延伸出去5.1 Python 中的单链表逆序写法如果你在做 Python 相关的数据结构实验也可以用 Python 实现一遍。Python 的类写法比 C 语言更贴近数据结构本身的表达但指针概念仍然存在只是没有显式表示为地址。class Node: def __init__(self, data): self.data data self.next None def reverse_iterative(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev这段代码的逻辑和 C 语言迭代版完全一致。唯一要注意的是Python 里没有指针类型变量可以灵活指向对象所以 prev、cur、nxt 这三个变量不需要提前声明类型。对于学习链表的人来说Python 版本更容易阅读C 版本更容易理解底层内存布局。我建议两个都写一遍。5.2 逆置的典型应用场景单链表逆置不只是实验课里的题目它在实际和面试场景里都经常出现。一个典型的应用是判断回文链表。一个字符串或数组如果正着读和倒着读一样就是回文。对链表来说一个直观的判断方案是先用快慢指针找到链表中点然后把后半段逆置再和前半段一一对比。这里就用到逆置操作。另一个常见场景是 K 个一组翻转链表。不是把整个链表逆置而是每隔 K 个节点翻转一次子链表。这个问题比整体逆置难一些但核心仍然是对“指针重连”的理解。如果你能把整表逆置写得非常熟练K 个一组翻转就有了基础。还有一类场景是倒序输出。题目要求从尾到头打印链表时一种办法是递归另一种办法是先把链表逆置再打印。虽然递归更省事但逆置后打印也是一种考察点。5.3 两个有序单链表合并的问题延伸材料里提到“已知两个长度为 m 和 n 的升序单链表”这实际上是另一个经典问题合并两个有序链表。它和建表、逆置之间的关系很有意思。合并两个升序链表时最自然的做法是使用尾插法依次比较两个链表的当前节点取较小的那个节点插入新链表中然后对应链表的指针后移。这个过程中你可以复用建表时学到的“尾插”思路。如果题目要求把结果反转成降序链表那可以先合并成升序链表再调用一次逆置函数。这样做代码简单但会多一次遍历。追求效率的话也可以在合并过程中直接采用头插法每次把较小节点插入新链表头部最后得到的就是降序链表。这里就能看出如果你把建表、头插、逆置这些基础操作理解透彻很多衍生题目都能组合着解出来。从学习路径来看单链表就是靠这一组基本操作支撑起来的。建表解决的是“怎么把数据变成链表”逆置解决的是“怎么把链表的顺序反过来”。把它们真正写明白之后后续的插入、删除、合并、排序都会顺很多。如果你还在练习阶段建议每周把建表和逆置的三种写法重新默写一遍慢慢地这些指针操作就会变成条件反射。
