尧图网站开发 
这次我们直接看单链表。很多同学刚接触“单链表”时第一反应是数组用着挺方便为什么还要单链表这个问题如果没想明白后面写插入、删除、逆序、合并的代码就会一直别扭。先把结论放在前面单链表是理解指针操作、内存管理和后续算法题的地基大部分数据结构实验、考研算法题和面试手撕代码都从单链表开始。这篇文章会覆盖单链表定义、结点结构设计、带头结点与不带头结点的区别、头插法、尾插法、按值删除、按位序插入、遍历查找、单链表逆序、合并两个升序单链表、判断链表是否有环并给出 C、Python、Java 三套可运行示例。代码全部可以直接复制编译运行适合正在上数据结构课、准备考研复试或刷 LeetCode 链表专题的读者。1. 单链表核心知识速览维度说明数据结构类型线性表的一种链式存储结构核心定义由若干结点串联组成每个结点包含数据域和指针域常用操作头插、尾插、按值删除、按位序插入、查找、遍历、反转、合并、判环时间复杂度按值查找 O(n)按位序插入 O(n)头插头删 O(1)尾插 O(1)维护尾指针时典型应用LRU 缓存、操作系统空闲存储管理、多项式表示、编辑器撤销栈、图的邻接表运行环境任意支持 C / Python / Java 的环境即可验证是否依赖 GPU不需要学习门槛需要理解结构体或类、指针或引用、内存分配与释放单链表和数组的核心区别是数组在内存中占用连续存储空间支持 O(1) 随机访问单链表不要求内存连续每个结点按需分配插入和删除操作只需要修改指针但是随机访问只能从头开始遍历时间复杂度是 O(n)。2. 单链表适用场景与使用边界先判断一下你什么时候该用单链表什么时候不该用适合使用单链表的场景频繁在头部或中间插入、删除元素且不便搬移大量数据。无法预估数据总量需要动态增长数组扩容成本高。需要实现诸如 LRU 缓存、任务队列、待办列表这类“逐步串联”的数据结构。学习指针、引用和内存管理。不适合使用单链表的场景需要频繁按下标随机访问元素。链表要遍历数组更合适。数据量小且长度固定。直接用数组更简单没必要引入结点分配开销。对缓存命中率要求高的高性能计算场景。链表结点在内存中可能分散CPU 缓存不友好。需要双向遍历的场景。单链表只有 next 指针回退需要重新从头遍历这种情况应使用双向链表。使用边界要说清楚单链表不是“更快的数组”而是“存储方式不同的线性表”。它牺牲了随机访问能力换来插入删除的灵活性和按需分配的内存使用方式。学习时不要只会背定义要通过代码实验去观察指针变化过程。3. 环境准备与前置条件单链表不需要 GPU、不需要 CUDA、不需要下载模型文件。准备一个能运行 C、Python 或 Java 的环境即可。推荐环境如下项目推荐方案C 语言Windows 下用 Dev-C 或 Visual StudioLinux/macOS 用 gccPythonPython 3.8 以上版本直接命令行运行JavaJDK 8 以上版本用 javac / java 编译运行调试辅助GDB 调试 C、IDE 断点或者用 print 输出结点地址可视化验证手动画图对比 next 指针变化或使用 Debug 查看链表展开C 语言示例编译命令gcc -g -o list list.c ./listPython 示例运行命令python3 list.pyJava 示例编译运行命令javac ListNode.java SingleLinkedList.java java SingleLinkedList如果本机没有安装编译器也可以使用在线 IDE。学习阶段建议优先在本地环境运行因为本地调试器能直接看到指针指向的地址这对理解单链表“串联”关系帮助很大。4. 单链表的定义与结点结构设计4.1 单链表是什么单链表是线性表的链式存储结构。它由一组结点组成每个结点存储一个数据元素和一个指向下一个结点的指针。最后一个结点的 next 指向空标记链表结束。单链表和数组一样描述的是“线性关系”但存储方式完全不同。数组是静态分配的连续空间链表是动态分配的离散空间依靠指针把结点串联起来。4.2 C 语言中的结构体定义在 C 语言中结点就是结构体变量。定义一个链表结点需要同时定义数据域和指针域。以数据域为 int 为例#include stdio.h #include stdlib.h #include stdbool.h typedef struct LNode { int data; struct LNode* next; } LNode;这里的关键点struct LNode* next是结点的指针域它指向下一个结点。如果链表到此结束则 next 为 NULL。很多初学者会把next理解成“另一个结点”更准确的说法是next保存的是下一个结点的地址。再看结构体变量的定义。上面代码中的这一句typedef struct LNode { int data; struct LNode* next; } LNode;等价于struct LNode { int data; struct LNode* next; }; typedef struct LNode LNode;定义完成后LNode node;表示定义一个结构体变量变量LNode* p;表示定义一个指向该结构体的指针变量。4.3 Python 中的类定义Python 没有指针但引用本身就具备指针语义。定义结点如下class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 中self.next保存的就是下一个 ListNode 对象的引用和 C 语言中的指针思路一致只是不需要手动管理内存。4.4 Java 中的结点定义Java 方式和 Python 类似public class ListNode { int val; ListNode next; public ListNode() {} public ListNode(int val) { this.val val; } }4.5 带头结点还是不带头结点这是一个很容易绕晕的问题。单链表有两种组织方式不带头结点链表第一个结点直接存储数据head 指向第一个数据结点。带头结点链表有一个额外的头结点它的 data 域不存储有效数据next 指向第一个数据结点。带头结点的好处很多插入第一个数据结点和插入其他位置的操作逻辑可以统一删除第一个数据结点时也不需要特殊处理头指针。单链表实验和大部分教材示例都建议使用带头结点。头结点的存在意义是“占位”它让空链表也有一个可管理的对象初始状态为只有一个头结点next 为 NULL。4.6 单链表定义小结定义一个单链表核心要素有三个数据域存储当前结点的值。指针域存储下一个结点的地址。头指针指向链表第一个结点是访问整个链表的入口。5. 单链表基本操作实现单链表的基本操作实验通常包括初始化、头插法创建、尾插法创建、按值删除、按位序插入、按值查找、遍历输出。下面给出一套完整可运行的 C 语言实现。5.1 初始化带头结点的单链表LNode* initList() { LNode* head (LNode*)malloc(sizeof(LNode)); head-data 0; head-next NULL; return head; }5.2 头插法创建单链表头插法每次把新结点插到头结点后面。特点是最后插入的结点会出现在链表最前面相当于逆序建表。void createByHead(LNode* head, int arr[], int n) { for (int i 0; i n; i) { LNode* s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next head-next; head-next s; } }执行顺序可以这样理解先让新结点指向原来的第一个数据结点再让头结点的 next 指向新结点。顺序不能反过来。如果先执行head-next s原来的链表就会丢失。5.3 尾插法创建单链表尾插法每次把新结点放到链表尾部。为了不每次遍历到尾结点需要用一个 tail 指针记录当前尾部结点。void createByTail(LNode* head, int arr[], int n) { LNode* tail head; for (int i 0; i n; i) { LNode* s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; tail s; } }尾插法保持了原始数据的相对顺序是实验中更常用的建表方式。5.4 遍历输出void printList(LNode* head) { LNode* p head-next; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }5.5 按值查找LNode* findByValue(LNode* head, int value) { LNode* p head-next; while (p ! NULL) { if (p-data value) { return p; } p p-next; } return NULL; }5.6 按位序插入在第 position 个位置插入结点position 从 1 开始计数。需要先找到第 position-1 个结点。bool insertByPosition(LNode* head, int position, int value) { LNode* p head; int i 0; while (p ! NULL i position - 1) { p p-next; i; } if (p NULL) { return false; } LNode* s (LNode*)malloc(sizeof(LNode)); s-data value; s-next p-next; p-next s; return true; }5.7 按值删除删除第一个值为 value 的结点。因为要修改前驱结点的 next所以需要找到待删除结点的前驱。bool deleteByValue(LNode* head, int value) { LNode* p head; while (p-next ! NULL) { if (p-next-data value) { LNode* q p-next; p-next q-next; free(q); return true; } p p-next; } return false; }5.8 释放整个链表手动管理内存的 C 代码在程序结束前要释放所有结点包括头结点。void freeList(LNode* head) { LNode* p head; while (p ! NULL) { LNode* next p-next; free(p); p next; } }5.9 主函数测试int main() { int arr[] {1, 2, 3, 4, 5}; int n sizeof(arr) / sizeof(arr[0]); LNode* head initList(); createByTail(head, arr, n); printf(尾插法结果\n); printList(head); LNode* found findByValue(head, 3); printf(查找值为3的结点%s\n, found ! NULL ? 找到 : 未找到); insertByPosition(head, 2, 99); printf(插入99到第2位后\n); printList(head); deleteByValue(head, 4); printf(删除值为4的结点后\n); printList(head); freeList(head); return 0; }运行结果尾插法结果 1 - 2 - 3 - 4 - 5 - NULL 查找值为3的结点找到 插入99到第2位后 1 - 99 - 2 - 3 - 4 - 5 - NULL 删除值为4的结点后 1 - 99 - 2 - 3 - 5 - NULL6. 单链表功能测试与效果验证基本操作写完以后建议按照下面这套顺序验证不要只看代码逻辑。6.1 测试目的验证单链表的创建、插入、删除和查找功能是否符合预期同时观察边界条件是否处理正确。6.2 测试用例建议测试场景输入预期结果空链表尾插初始化后不插入任何值printList 输出 NULL头插法依次插入 1,2,3结果为 3 - 2 - 1 - NULL尾插法依次插入 1,2,3结果为 1 - 2 - 3 - NULL删除头结点后的第一个结点链表 1,2,3删除 1结果为 2 - 3 - NULL删除不存在结点链表中没有 99返回 false链表不变在第 1 位插入链表 1,2插入 0 到第1位结果为 0 - 1 - 2 - NULL在末尾后一位插入链表 1,2在第3位插入 3结果为 1 - 2 - 3 - NULL插入位置过大链表 1,2在第5位插入返回 false6.3 判断是否成功判定的标准是遍历结果和预期一致且没有丢结点、没有内存泄漏。C 语言环境下可以使用 Valgrind 检查内存泄漏valgrind --leak-checkfull ./list如果显示no leaks are possible说明所有结点都被正确释放。6.4 常见失败原因插入时先改 head-next导致原链表断开。删除时没有保存待删除结点的 nextfree 之后丢失后续链表。遍历时循环条件写错多走一步访问 NULL 导致段错误。malloc 后忘记判断是否为空。忘记释放不再使用的结点。7. 单链表进阶操作逆序、合并、判环基础操作跑通后可以做三件事单链表逆序、合并两个升序单链表、判断链表是否有环。这三个操作是单链表实验中出镜率最高的题目也是 LeetCode 上的经典原题。7.1 单链表逆序Python 版本的迭代式逆序实现如下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这里的核心思想是用 cur 指向当前要处理的结点用 prev 记录已经处理好的链表头用 nxt 保存 cur 原来的下一个结点否则修改 next 之后就会丢失后续链表。C 语言版本void reverseList(LNode* head) { LNode* prev NULL; LNode* cur head-next; while (cur ! NULL) { LNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } head-next prev; }Java 版本public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; }逆序测试用例链表 1 - 2 - 3 - 4 - 5逆序后为 5 - 4 - 3 - 2 - 1。递归方法也能实现逆序但迭代方法空间复杂度只有 O(1)更推荐先掌握。7.2 合并两个升序单链表已知两个长度为 m 和 n 的升序单链表将它们合并为一个有序链表是单链表考研题和面试题中的高频题目。要求是两个链表依然升序。Python 实现def merge_two_lists(a, b): dummy ListNode(0) tail dummy while a is not None and b is not None: if a.val b.val: tail.next a a a.next else: tail.next b b b.next tail tail.next if a is not None: tail.next a if b is not None: tail.next b return dummy.nextJava 实现public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode tail dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { tail.next l1; l1 l1.next; } else { tail.next l2; l2 l2.next; } tail tail.next; } tail.next (l1 ! null) ? l1 : l2; return dummy.next; }合并操作的解题要点有两个。第一使用 dummy 结点避免处理“链表头最终是 a 还是 b”的分支判断。第二循环结束后最多还剩一条链表未遍历完直接把尾指针接到剩余链表头部即可。测试用例输入输出a 1 - 3 - 5b 2 - 4 - 61 - 2 - 3 - 4 - 5 - 6a 空b 1 - 21 - 2a 1 - 2b 空1 - 2a 1 - 2b 1 - 31 - 1 - 2 - 37.3 判断单链表是否有环使用快慢指针慢指针每次走一步快指针每次走两步。如果链表有环快指针最终会追上慢指针如果无环快指针会先走到 NULL。def has_cycle(head): slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow fast: return True return False这个操作不修改链表结构只做检测在面试中经常作为附加题出现。8. 单链表复杂度分析与性能观察时间复杂度汇总操作带头结点单链表时间复杂度说明头插法创建 n 个结点O(n)每次插入 O(1)共 n 次尾插法创建 n 个结点O(n)维护尾指针后每次插入 O(1)按值查找O(n)最坏情况遍历整条链表按位序插入O(n)需要先找到前驱结点按值删除O(n)需要先找到前驱结点删除给定指针指向的结点O(1)用后一结点覆盖当前结点再删除后一结点头插、头删O(1)直接修改头结点 next逆序O(n)只遍历一遍链表合并两个升序链表O(mn)两个链表各遍历一次判环O(n)快慢指针最多遍历一遍空间复杂度方面基本操作额外空间为 O(1)合并和逆序的迭代实现额外空间也是 O(1)。递归实现逆序或合并时递归栈深度为 O(n)需要注意。观察性能时比较典型的现象是当链表规模增大时按值查找和尾插法不维护尾指针会明显变慢因为每次都要从头遍历。这就是为什么在实验中使用尾插法时一定要维护 tail 指针。单链表在性能上还有一个特点内存碎片化。C 语言中每次 malloc 一个结点结点在堆中的地址不一定连续遍历链表时 CPU 缓存命中率不如数组。数据量很大时即使时间复杂度和数组操作同为 O(n)链表可能仍然更慢。这是链表的固有特性不是代码问题。9. 单链表常见问题与排查方法问题现象可能原因排查方式解决方案程序运行时崩溃提示段错误访问了 NULL 指针检查循环条件中是否有p-next为 NULL 的情况使用前判断 p 是否为空插入删除时先找到前驱遍历输出缺失部分结点插入时修改指针顺序错误对照头插法、尾插法步骤检查插入步骤应为新结点先指向后继再连接前驱删除后链表断开free 前没有保存下一个结点地址检查删除分支代码先用q p-next保存待删结点修改 p-next 后再 free内存泄漏malloc 的结点没有被 free使用 Valgrind 检查遍历链表释放所有结点包括头结点链表逆序后尾部丢失修改 cur-next 后没有保存 nxt检查逆序循环变量先保存nxt cur-next再修改 cur-next合并有序链表缺少剩余部分循环结束后没有接上剩余链表检查合并函数循环后的代码循环结束后tail.next a if a else b判环函数死循环快指针步长写成 fast fast.next误认为两步检查循环中 fast 的移动快指针移动两格fast fast.next.next插入位置计算不准多插入一位或漏插入position 计数理解有误打印查找前驱的 i 变化按位序插入时 position 从 1 开始需要找第 position-1 个结点遇到链表问题第一件事不是改代码而是画出当前链表和指针变化图。把 head、p、s、prev、cur、nxt 这些指针用箭头表示每一步修改都对应一条赋值语句只要箭头画正确代码自然写正确。10. 单链表最佳实践与使用建议结合实验和刷题经验给出一套可以直接沿用的实践建议。10.1 统一使用带头结点除非题目明确要求不带头结点否则建议统一带头结点。带头结点可以消除空链表和非空链表操作的差异删除首元结点时不需要修改头指针代码逻辑更简洁。10.2 建表优先使用尾插法如果数据顺序有意义优先使用尾插法。头插法虽然代码看着简单但会让数据逆序容易造成误解。在单链表基本操作实验中尾插法配合 tail 指针是更稳妥的方案。10.3 善用 dummy 结点在合并有序链表、删除倒数第 N 个结点等场景中使用 dummy 结点可以减少边界判断。它的核心价值是提供一个虚拟的前驱避免单独处理头结点被修改的情况。10.4 双指针技巧值得重点掌握链表中大量算法题的优化思路都来自双指针。快慢指针可以判环、找中点、找倒数第 K 个结点前后指针可以在一次遍历内完成逆序临时指针可以在交换结点时不丢失链表引用。10.5 分离逻辑测试和效果复核写链表代码时先跑小规模用例比如 3 个结点以内的插入删除打印每一步结果。确认无误后再跑大规模数据。实验报告中应当包含测试输入、实际输出和结果分析而不只是贴一段代码。10.6 注意代码规范与算法复用deleteNode、isEmpty、getSize这类工具函数可以单独封装。C 语言中封装成函数指针结构体Java 中使用LinkedList类Python 中定义LinkedList类统一管理。这和实际工程中把链表封装成可复用组件的思路一致。10.7 应用场景落地实现 LRU 缓存时哈希表负责 O(1) 查找单链表或双向链表负责记录访问顺序。实现任务队列时单链表天然支持头部出队、尾部入队比数组扩容方案更灵活。实现多项式加法时单链表结点可以存储系数和指数便于动态维护多项式项数。11. 总结单链表定义和实现的核心并不复杂一个数据域、一个指针域加上对指针的插入、删除和遍历操作。真正难的是理解指针在内存中如何串联结点以及如何通过前驱结点完成插入和删除。建议先跑通这篇里的 C 语言完整示例再用 Python 实现逆序和合并两个升序链表最后用 Java 手写一遍判环。三个语言各写一遍单链表的基本操作实验基本就掌握了。最先要验证的功能是头插法和尾插法创建链表最容易踩的坑是插入时指针修改顺序和删除时丢失后继结点。后续可以从单链表扩展到双向链表、循环链表、静态链表再进阶到 LRU 缓存、链表排序、相交链表、回文链表等综合题。数据结构这一块单链表的实现会了后面很多链式结构都顺理成章。建议收藏备用写实验报告或刷题前拿出来过一遍。 
这次我们直接看单链表。很多同学刚接触“单链表”时第一反应是数组用着挺方便为什么还要单链表这个问题如果没想明白后面写插入、删除、逆序、合并的代码就会一直别扭。先把结论放在前面单链表是理解指针操作、内存管理和后续算法题的地基大部分数据结构实验、考研算法题和面试手撕代码都从单链表开始。这篇文章会覆盖单链表定义、结点结构设计、带头结点与不带头结点的区别、头插法、尾插法、按值删除、按位序插入、遍历查找、单链表逆序、合并两个升序单链表、判断链表是否有环并给出 C、Python、Java 三套可运行示例。代码全部可以直接复制编译运行适合正在上数据结构课、准备考研复试或刷 LeetCode 链表专题的读者。1. 单链表核心知识速览维度说明数据结构类型线性表的一种链式存储结构核心定义由若干结点串联组成每个结点包含数据域和指针域常用操作头插、尾插、按值删除、按位序插入、查找、遍历、反转、合并、判环时间复杂度按值查找 O(n)按位序插入 O(n)头插头删 O(1)尾插 O(1)维护尾指针时典型应用LRU 缓存、操作系统空闲存储管理、多项式表示、编辑器撤销栈、图的邻接表运行环境任意支持 C / Python / Java 的环境即可验证是否依赖 GPU不需要学习门槛需要理解结构体或类、指针或引用、内存分配与释放单链表和数组的核心区别是数组在内存中占用连续存储空间支持 O(1) 随机访问单链表不要求内存连续每个结点按需分配插入和删除操作只需要修改指针但是随机访问只能从头开始遍历时间复杂度是 O(n)。2. 单链表适用场景与使用边界先判断一下你什么时候该用单链表什么时候不该用适合使用单链表的场景频繁在头部或中间插入、删除元素且不便搬移大量数据。无法预估数据总量需要动态增长数组扩容成本高。需要实现诸如 LRU 缓存、任务队列、待办列表这类“逐步串联”的数据结构。学习指针、引用和内存管理。不适合使用单链表的场景需要频繁按下标随机访问元素。链表要遍历数组更合适。数据量小且长度固定。直接用数组更简单没必要引入结点分配开销。对缓存命中率要求高的高性能计算场景。链表结点在内存中可能分散CPU 缓存不友好。需要双向遍历的场景。单链表只有 next 指针回退需要重新从头遍历这种情况应使用双向链表。使用边界要说清楚单链表不是“更快的数组”而是“存储方式不同的线性表”。它牺牲了随机访问能力换来插入删除的灵活性和按需分配的内存使用方式。学习时不要只会背定义要通过代码实验去观察指针变化过程。3. 环境准备与前置条件单链表不需要 GPU、不需要 CUDA、不需要下载模型文件。准备一个能运行 C、Python 或 Java 的环境即可。推荐环境如下项目推荐方案C 语言Windows 下用 Dev-C 或 Visual StudioLinux/macOS 用 gccPythonPython 3.8 以上版本直接命令行运行JavaJDK 8 以上版本用 javac / java 编译运行调试辅助GDB 调试 C、IDE 断点或者用 print 输出结点地址可视化验证手动画图对比 next 指针变化或使用 Debug 查看链表展开C 语言示例编译命令gcc -g -o list list.c ./listPython 示例运行命令python3 list.pyJava 示例编译运行命令javac ListNode.java SingleLinkedList.java java SingleLinkedList如果本机没有安装编译器也可以使用在线 IDE。学习阶段建议优先在本地环境运行因为本地调试器能直接看到指针指向的地址这对理解单链表“串联”关系帮助很大。4. 单链表的定义与结点结构设计4.1 单链表是什么单链表是线性表的链式存储结构。它由一组结点组成每个结点存储一个数据元素和一个指向下一个结点的指针。最后一个结点的 next 指向空标记链表结束。单链表和数组一样描述的是“线性关系”但存储方式完全不同。数组是静态分配的连续空间链表是动态分配的离散空间依靠指针把结点串联起来。4.2 C 语言中的结构体定义在 C 语言中结点就是结构体变量。定义一个链表结点需要同时定义数据域和指针域。以数据域为 int 为例#include stdio.h #include stdlib.h #include stdbool.h typedef struct LNode { int data; struct LNode* next; } LNode;这里的关键点struct LNode* next是结点的指针域它指向下一个结点。如果链表到此结束则 next 为 NULL。很多初学者会把next理解成“另一个结点”更准确的说法是next保存的是下一个结点的地址。再看结构体变量的定义。上面代码中的这一句typedef struct LNode { int data; struct LNode* next; } LNode;等价于struct LNode { int data; struct LNode* next; }; typedef struct LNode LNode;定义完成后LNode node;表示定义一个结构体变量变量LNode* p;表示定义一个指向该结构体的指针变量。4.3 Python 中的类定义Python 没有指针但引用本身就具备指针语义。定义结点如下class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 中self.next保存的就是下一个 ListNode 对象的引用和 C 语言中的指针思路一致只是不需要手动管理内存。4.4 Java 中的结点定义Java 方式和 Python 类似public class ListNode { int val; ListNode next; public ListNode() {} public ListNode(int val) { this.val val; } }4.5 带头结点还是不带头结点这是一个很容易绕晕的问题。单链表有两种组织方式不带头结点链表第一个结点直接存储数据head 指向第一个数据结点。带头结点链表有一个额外的头结点它的 data 域不存储有效数据next 指向第一个数据结点。带头结点的好处很多插入第一个数据结点和插入其他位置的操作逻辑可以统一删除第一个数据结点时也不需要特殊处理头指针。单链表实验和大部分教材示例都建议使用带头结点。头结点的存在意义是“占位”它让空链表也有一个可管理的对象初始状态为只有一个头结点next 为 NULL。4.6 单链表定义小结定义一个单链表核心要素有三个数据域存储当前结点的值。指针域存储下一个结点的地址。头指针指向链表第一个结点是访问整个链表的入口。5. 单链表基本操作实现单链表的基本操作实验通常包括初始化、头插法创建、尾插法创建、按值删除、按位序插入、按值查找、遍历输出。下面给出一套完整可运行的 C 语言实现。5.1 初始化带头结点的单链表LNode* initList() { LNode* head (LNode*)malloc(sizeof(LNode)); head-data 0; head-next NULL; return head; }5.2 头插法创建单链表头插法每次把新结点插到头结点后面。特点是最后插入的结点会出现在链表最前面相当于逆序建表。void createByHead(LNode* head, int arr[], int n) { for (int i 0; i n; i) { LNode* s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next head-next; head-next s; } }执行顺序可以这样理解先让新结点指向原来的第一个数据结点再让头结点的 next 指向新结点。顺序不能反过来。如果先执行head-next s原来的链表就会丢失。5.3 尾插法创建单链表尾插法每次把新结点放到链表尾部。为了不每次遍历到尾结点需要用一个 tail 指针记录当前尾部结点。void createByTail(LNode* head, int arr[], int n) { LNode* tail head; for (int i 0; i n; i) { LNode* s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; tail s; } }尾插法保持了原始数据的相对顺序是实验中更常用的建表方式。5.4 遍历输出void printList(LNode* head) { LNode* p head-next; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }5.5 按值查找LNode* findByValue(LNode* head, int value) { LNode* p head-next; while (p ! NULL) { if (p-data value) { return p; } p p-next; } return NULL; }5.6 按位序插入在第 position 个位置插入结点position 从 1 开始计数。需要先找到第 position-1 个结点。bool insertByPosition(LNode* head, int position, int value) { LNode* p head; int i 0; while (p ! NULL i position - 1) { p p-next; i; } if (p NULL) { return false; } LNode* s (LNode*)malloc(sizeof(LNode)); s-data value; s-next p-next; p-next s; return true; }5.7 按值删除删除第一个值为 value 的结点。因为要修改前驱结点的 next所以需要找到待删除结点的前驱。bool deleteByValue(LNode* head, int value) { LNode* p head; while (p-next ! NULL) { if (p-next-data value) { LNode* q p-next; p-next q-next; free(q); return true; } p p-next; } return false; }5.8 释放整个链表手动管理内存的 C 代码在程序结束前要释放所有结点包括头结点。void freeList(LNode* head) { LNode* p head; while (p ! NULL) { LNode* next p-next; free(p); p next; } }5.9 主函数测试int main() { int arr[] {1, 2, 3, 4, 5}; int n sizeof(arr) / sizeof(arr[0]); LNode* head initList(); createByTail(head, arr, n); printf(尾插法结果\n); printList(head); LNode* found findByValue(head, 3); printf(查找值为3的结点%s\n, found ! NULL ? 找到 : 未找到); insertByPosition(head, 2, 99); printf(插入99到第2位后\n); printList(head); deleteByValue(head, 4); printf(删除值为4的结点后\n); printList(head); freeList(head); return 0; }运行结果尾插法结果 1 - 2 - 3 - 4 - 5 - NULL 查找值为3的结点找到 插入99到第2位后 1 - 99 - 2 - 3 - 4 - 5 - NULL 删除值为4的结点后 1 - 99 - 2 - 3 - 5 - NULL6. 单链表功能测试与效果验证基本操作写完以后建议按照下面这套顺序验证不要只看代码逻辑。6.1 测试目的验证单链表的创建、插入、删除和查找功能是否符合预期同时观察边界条件是否处理正确。6.2 测试用例建议测试场景输入预期结果空链表尾插初始化后不插入任何值printList 输出 NULL头插法依次插入 1,2,3结果为 3 - 2 - 1 - NULL尾插法依次插入 1,2,3结果为 1 - 2 - 3 - NULL删除头结点后的第一个结点链表 1,2,3删除 1结果为 2 - 3 - NULL删除不存在结点链表中没有 99返回 false链表不变在第 1 位插入链表 1,2插入 0 到第1位结果为 0 - 1 - 2 - NULL在末尾后一位插入链表 1,2在第3位插入 3结果为 1 - 2 - 3 - NULL插入位置过大链表 1,2在第5位插入返回 false6.3 判断是否成功判定的标准是遍历结果和预期一致且没有丢结点、没有内存泄漏。C 语言环境下可以使用 Valgrind 检查内存泄漏valgrind --leak-checkfull ./list如果显示no leaks are possible说明所有结点都被正确释放。6.4 常见失败原因插入时先改 head-next导致原链表断开。删除时没有保存待删除结点的 nextfree 之后丢失后续链表。遍历时循环条件写错多走一步访问 NULL 导致段错误。malloc 后忘记判断是否为空。忘记释放不再使用的结点。7. 单链表进阶操作逆序、合并、判环基础操作跑通后可以做三件事单链表逆序、合并两个升序单链表、判断链表是否有环。这三个操作是单链表实验中出镜率最高的题目也是 LeetCode 上的经典原题。7.1 单链表逆序Python 版本的迭代式逆序实现如下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这里的核心思想是用 cur 指向当前要处理的结点用 prev 记录已经处理好的链表头用 nxt 保存 cur 原来的下一个结点否则修改 next 之后就会丢失后续链表。C 语言版本void reverseList(LNode* head) { LNode* prev NULL; LNode* cur head-next; while (cur ! NULL) { LNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } head-next prev; }Java 版本public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; }逆序测试用例链表 1 - 2 - 3 - 4 - 5逆序后为 5 - 4 - 3 - 2 - 1。递归方法也能实现逆序但迭代方法空间复杂度只有 O(1)更推荐先掌握。7.2 合并两个升序单链表已知两个长度为 m 和 n 的升序单链表将它们合并为一个有序链表是单链表考研题和面试题中的高频题目。要求是两个链表依然升序。Python 实现def merge_two_lists(a, b): dummy ListNode(0) tail dummy while a is not None and b is not None: if a.val b.val: tail.next a a a.next else: tail.next b b b.next tail tail.next if a is not None: tail.next a if b is not None: tail.next b return dummy.nextJava 实现public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode tail dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { tail.next l1; l1 l1.next; } else { tail.next l2; l2 l2.next; } tail tail.next; } tail.next (l1 ! null) ? l1 : l2; return dummy.next; }合并操作的解题要点有两个。第一使用 dummy 结点避免处理“链表头最终是 a 还是 b”的分支判断。第二循环结束后最多还剩一条链表未遍历完直接把尾指针接到剩余链表头部即可。测试用例输入输出a 1 - 3 - 5b 2 - 4 - 61 - 2 - 3 - 4 - 5 - 6a 空b 1 - 21 - 2a 1 - 2b 空1 - 2a 1 - 2b 1 - 31 - 1 - 2 - 37.3 判断单链表是否有环使用快慢指针慢指针每次走一步快指针每次走两步。如果链表有环快指针最终会追上慢指针如果无环快指针会先走到 NULL。def has_cycle(head): slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow fast: return True return False这个操作不修改链表结构只做检测在面试中经常作为附加题出现。8. 单链表复杂度分析与性能观察时间复杂度汇总操作带头结点单链表时间复杂度说明头插法创建 n 个结点O(n)每次插入 O(1)共 n 次尾插法创建 n 个结点O(n)维护尾指针后每次插入 O(1)按值查找O(n)最坏情况遍历整条链表按位序插入O(n)需要先找到前驱结点按值删除O(n)需要先找到前驱结点删除给定指针指向的结点O(1)用后一结点覆盖当前结点再删除后一结点头插、头删O(1)直接修改头结点 next逆序O(n)只遍历一遍链表合并两个升序链表O(mn)两个链表各遍历一次判环O(n)快慢指针最多遍历一遍空间复杂度方面基本操作额外空间为 O(1)合并和逆序的迭代实现额外空间也是 O(1)。递归实现逆序或合并时递归栈深度为 O(n)需要注意。观察性能时比较典型的现象是当链表规模增大时按值查找和尾插法不维护尾指针会明显变慢因为每次都要从头遍历。这就是为什么在实验中使用尾插法时一定要维护 tail 指针。单链表在性能上还有一个特点内存碎片化。C 语言中每次 malloc 一个结点结点在堆中的地址不一定连续遍历链表时 CPU 缓存命中率不如数组。数据量很大时即使时间复杂度和数组操作同为 O(n)链表可能仍然更慢。这是链表的固有特性不是代码问题。9. 单链表常见问题与排查方法问题现象可能原因排查方式解决方案程序运行时崩溃提示段错误访问了 NULL 指针检查循环条件中是否有p-next为 NULL 的情况使用前判断 p 是否为空插入删除时先找到前驱遍历输出缺失部分结点插入时修改指针顺序错误对照头插法、尾插法步骤检查插入步骤应为新结点先指向后继再连接前驱删除后链表断开free 前没有保存下一个结点地址检查删除分支代码先用q p-next保存待删结点修改 p-next 后再 free内存泄漏malloc 的结点没有被 free使用 Valgrind 检查遍历链表释放所有结点包括头结点链表逆序后尾部丢失修改 cur-next 后没有保存 nxt检查逆序循环变量先保存nxt cur-next再修改 cur-next合并有序链表缺少剩余部分循环结束后没有接上剩余链表检查合并函数循环后的代码循环结束后tail.next a if a else b判环函数死循环快指针步长写成 fast fast.next误认为两步检查循环中 fast 的移动快指针移动两格fast fast.next.next插入位置计算不准多插入一位或漏插入position 计数理解有误打印查找前驱的 i 变化按位序插入时 position 从 1 开始需要找第 position-1 个结点遇到链表问题第一件事不是改代码而是画出当前链表和指针变化图。把 head、p、s、prev、cur、nxt 这些指针用箭头表示每一步修改都对应一条赋值语句只要箭头画正确代码自然写正确。10. 单链表最佳实践与使用建议结合实验和刷题经验给出一套可以直接沿用的实践建议。10.1 统一使用带头结点除非题目明确要求不带头结点否则建议统一带头结点。带头结点可以消除空链表和非空链表操作的差异删除首元结点时不需要修改头指针代码逻辑更简洁。10.2 建表优先使用尾插法如果数据顺序有意义优先使用尾插法。头插法虽然代码看着简单但会让数据逆序容易造成误解。在单链表基本操作实验中尾插法配合 tail 指针是更稳妥的方案。10.3 善用 dummy 结点在合并有序链表、删除倒数第 N 个结点等场景中使用 dummy 结点可以减少边界判断。它的核心价值是提供一个虚拟的前驱避免单独处理头结点被修改的情况。10.4 双指针技巧值得重点掌握链表中大量算法题的优化思路都来自双指针。快慢指针可以判环、找中点、找倒数第 K 个结点前后指针可以在一次遍历内完成逆序临时指针可以在交换结点时不丢失链表引用。10.5 分离逻辑测试和效果复核写链表代码时先跑小规模用例比如 3 个结点以内的插入删除打印每一步结果。确认无误后再跑大规模数据。实验报告中应当包含测试输入、实际输出和结果分析而不只是贴一段代码。10.6 注意代码规范与算法复用deleteNode、isEmpty、getSize这类工具函数可以单独封装。C 语言中封装成函数指针结构体Java 中使用LinkedList类Python 中定义LinkedList类统一管理。这和实际工程中把链表封装成可复用组件的思路一致。10.7 应用场景落地实现 LRU 缓存时哈希表负责 O(1) 查找单链表或双向链表负责记录访问顺序。实现任务队列时单链表天然支持头部出队、尾部入队比数组扩容方案更灵活。实现多项式加法时单链表结点可以存储系数和指数便于动态维护多项式项数。11. 总结单链表定义和实现的核心并不复杂一个数据域、一个指针域加上对指针的插入、删除和遍历操作。真正难的是理解指针在内存中如何串联结点以及如何通过前驱结点完成插入和删除。建议先跑通这篇里的 C 语言完整示例再用 Python 实现逆序和合并两个升序链表最后用 Java 手写一遍判环。三个语言各写一遍单链表的基本操作实验基本就掌握了。最先要验证的功能是头插法和尾插法创建链表最容易踩的坑是插入时指针修改顺序和删除时丢失后继结点。后续可以从单链表扩展到双向链表、循环链表、静态链表再进阶到 LRU 缓存、链表排序、相交链表、回文链表等综合题。数据结构这一块单链表的实现会了后面很多链式结构都顺理成章。建议收藏备用写实验报告或刷题前拿出来过一遍。