算法|??《画解数据结构》七个动图，画解链表?? 链表|单向链表|《画解数据结构

本文已收录于专栏 《画解数据结构》
零、前言

??「数据结构」 和 「算法」 是密不可分的，两者往往是「相辅相成」的存在，所以，在学习 「数据结构」 的过程中，不免会遇到各种「算法」。
??到底是先学数据结构，还是先学算法，我认为不必纠结这个问题，一定是一起学的。
??数据结构常用的操作一般为：「增」「删」「改」「查」。基本上所有的数据结构都是围绕这几个操作进行展开的。
??那么这篇文章，作者将用 「七张动图」 来阐述一种最基础的链式结构

「单向链表」

文章图片

饭不食，水不饮，题必须刷
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
LeetCode 太难？先看简单题！ 《C语言入门100例》
数据结构难？不存在的！ 《画解数据结构》
闭关刷 LeetCode，剑指大厂Offer！ 《LeetCode 刷题指引》
LeetCode 太简单？算法学起来！ 《夜深人静写算法》
??今天要讲的内容，浓缩一下就是下面这张图：
??看不懂没有关系，我会把它拆开来一个一个讲，首先来看一些简单的概念。

文章目录

零、前言
一、概念
- 1、链表定义
- 2、结点结构体定义
- 3、结点的创建
二、链表的创建 - 尾插法
- 1、算法描述
- 2、动画演示
- 3、源码详解
三、链表的创建 - 头插法
- 1、算法描述
- 2、动画演示
- 3、源码详解
四、链表的打印
- 1、打印的作用
- 2、源码详解
- 3、测试用例
五、链表元素的索引
- 1、算法描述
- 2、动画演示
- 3、源码详解
- 4、测试用例
- 5、算法分析
- - 1）时间复杂度
  - 2）空间复杂度
六、链表元素的查找
- 1、算法描述
- 2、动画演示
- 3、源码详解
- 4、测试用例
- 5、算法分析
- - 1）时间复杂度
  - 2）空间复杂度
七、链表结点的插入
- 1、算法描述
- 2、动画演示
- 3、源码详解
- 4、测试用例
- 5、算法分析
- - 1）时间复杂度
  - 2）空间复杂度
八、链表结点的删除
- 1、算法描述
- 2、动画演示
- 3、源码详解
- 4、测试用例
- 5、算法分析
- - 1）时间复杂度
  - 2）空间复杂度
九、链表的销毁
- 1、算法描述
- 2、动画演示
- 3、源码详解
- 4、测试用例
- 5、算法分析
- - 1）时间复杂度
  - 2）空间复杂度
十、链表的优缺点
- 1、优点
- 2、缺点

一、概念

对于顺序存储的结构，如数组，最大的缺点就是：插入和删除的时候需要移动大量的元素。所以，基于前人的智慧，他们发明了链表。

1、链表定义

??链表是由一个个结点组成，每个结点之间通过链接关系串联起来，每个结点都有一个后继节点，最后一个结点的后继结点为空结点。如下图所示：

文章图片

由链接关系A -> B组织起来的两个结点，B被称为A的后继结点，A被称为B的前驱结点。
链表分为单向链表、双向链表、循环链表等等，本文要介绍的链表是单向链表。
由于链表是由一个个结点组成，所以我们先来看下结点的实现。

2、结点结构体定义

typedef int DataType; struct ListNode {DataType data; // (1) ListNode *next; // (2) };

( 1 ) (1) (1) 数据域：可以是任意类型，由编码的人自行指定；这段代码中，利用typedef将它和int同名，本文的数据域也会全部采用int类型进行讲解；
( 2 ) (2) (2) 指针域：指向后继结点的地址；
一个结点包含的两部分如下图所示：

文章图片

3、结点的创建

我们通过 C语言中的库函数malloc来创建一个链表结点，然后对数据域和指针域进行赋值，代码实现如下：

ListNode *ListCreateNode(DataType data) {ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); // (1) node->data = https://www.it610.com/article/data; // (2) node->next = NULL; // (3) return node; // (4) }

( 1 ) (1) (1) 利用系统库函数malloc分配一块内存空间，用来存放ListNode即链表结点对象；
( 2 ) (2) (2) 将数据域置为函数传参data；
( 3 ) (3) (3) 将指针域置空，代表这是一个孤立的链表结点；
( 4 ) (4) (4) 返回这个结点的指针。
创建完毕以后，这个孤立结点如下所示：

文章图片

二、链表的创建 - 尾插法

那么接下来，让我们看下如何通过一个数组中的数据来创建一个链表。

1、算法描述

??首先介绍尾插法，顾名思义，即从链表尾部插入的意思，就是记录一个链表尾结点，然后遍历给定数组，将数组元素一个一个插到链表的尾部，每插入一个结点，则将它更新为新的链表尾结点。注意初始情况下，链表尾结点为空。

2、动画演示

上图演示的是尾插法的整个过程，其中：
??head 代表链表头结点，创建完一个结点以后，它就保持不变了；
??tail 代表链表尾结点，即动图中的 绿色结点；
??vtx 代表正在插入链表尾部的结点，即动图中的 橙色结点，插入完毕以后，vtx 变成 tail；

看完这个动图，你应该已经大致理解了链表的创建过程。那么接下来，我们用程序语言来描述一下整个过程，这里采用的是 C语言的形式，如果你是 Java、C#、Python 技术栈的，也可以试着写出自己的版本。
语言并不是关键，思维才是关键。

3、源码详解

C语言实现如下：

ListNode *ListCreateListByTail(int n, int a[]) {ListNode *head, *tail, *vtx; // (1) int idx; if(n <= 0) return NULL; // (2) idx = 0; vtx = ListCreateNode(a[0]); // (3) head = tail = vtx; // (4) while(++idx < n) { // (5) vtx = ListCreateNode(a[idx]); // (6) tail->next = vtx; // (7) tail = vtx; // (8) } return head; // (9) }

对应的注释如下：
?? ( 1 ) (1) (1) head存储头结点的地址，tail存储尾结点的地址，vtx存储当前正在插入结点的地址；
?? ( 2 ) (2) (2) 当需要创建的元素个数为 0 时，直接返回空链表；
?? ( 3 ) (3) (3) 创建一个数据域为a[0]的链表结点；
?? ( 4 ) (4) (4) 由于初始情况下只有一个结点，所以将链表头结点head和链表尾结点tail都置为vtx；
?? ( 5 ) (5) (5) 从数组第 1 个元素 (0 - based) 开始，循环遍历数组；
?? ( 6 ) (6) (6) 由于数组中第 0 个元素已经创建过了，所以这里只需要对除了第 0 个元素以外的数据创建链表结点；
?? ( 7 ) (7) (7) 结点创建出来后，将当前链表尾结点tail的后继结点置为vtx；
?? ( 8 ) (8) (8) 将最近创建的结点vtx作为新的链表尾结点；
?? ( 9 ) (9) (9) 返回链表头结点；

尾插法比较符合直观的思维逻辑，但是就代码量来说还是有点长（注意：在实现相同功能的情况下，代码应该是越简洁，越简单越好的）。
于是，我们引入了另一种创建链表的方式 —— 头插法。

三、链表的创建 - 头插法 1、算法描述

??头插法，顾名思义，就是每次从头结点前面进行插入，但是这样一来，就会导致插入的数据元素是逆序的，所以我们需要逆序访问数组执行插入，此所谓负负得正的思想。

它的特点是代码量短，且常数时间复杂度低。虽然没有尾插法那么直观，但是代码简洁，更加容易阅读。

2、动画演示

上图所示的是头插法的整个插入过程，其中：
??head 代表链表头结点，即动图中的 绿色结点，每新加一个结点，头结点就变成了新加入的结点；
??tail 代表链表尾结点，创建完一个结点以后，它就保持不变了；
??vtx 代表正在插入链表头部的结点，即动图中的 橙色结点，插入完毕以后，vtx 变成 head；

3、源码详解

ListNode *ListCreateListByHead(int n, int *a) {ListNode *head = NULL, *vtx; // (1) while(n--) { // (2) vtx = ListCreateNode(a[n]); // (3) vtx->next = head; // (4) head = vtx; // (5) } return head; // (6) }

对应的注释如下：
?? ( 1 ) (1) (1) head存储头结点的地址，初始为空链表， vtx存储当前正在插入结点的地址；
?? ( 2 ) (2) (2) 总共需要插入n n n 个结点，所以采用逆序的n n n 次循环；
?? ( 3 ) (3) (3) 创建一个元素值为a[i]的链表结点，注意，由于逆序，所以这里i i i 的取值为n ? 1 → 0 n-1 \to 0 n?1→0；
?? ( 4 ) (4) (4) 将当前创建的结点的后继结点置为链表的头结点head；
?? ( 5 ) (5) (5) 将链表头结点head置为vtx；
?? ( 6 ) (6) (6) 返回链表头结点；

头插法的代码量比尾插法少了三分之一，而且将创建结点的逻辑统一起来了。这句话什么意思呢？仔细观察可以发现，尾插法在实现过程中，ListCreateNode在代码里出现了两次，而头插法只出现了一次，将流程简化了，所以还是推荐使用头插法。

四、链表的打印 1、打印的作用

可视化能够帮助我们更好的理解数据结构。所以，对于一种数据结构，如何通过输出函数将它打印到控制台上，就成了我们接下来要做的事情。
我会用 C语言来实现，但是只要你掌握了这套自己验证的方法，那么就算用其他语言，一样可以验证自己代码的正确性。

那么，如何打印一个链表呢？我们可以这么思考：
??链表的每个结点都有一个后继结点，我们可以用A -> B代表结点B是结点A的后继结点，而对于最后一个结点而言，它的后继可以用NULL表示。所以，我们可以循环输出所有结点并且带上->，然后在最后加上NULL。

2、源码详解

C语言实现如下：

void ListPrint(ListNode *head) {ListNode *vtx = head; while(vtx) { // (1) printf("%d -> ", vtx->data); // (2) vtx = vtx->next; // (3) } printf("NULL\n"); // (4) }

对应的注释如下：
?? ( 1 ) (1) (1) 从头结点开始，循环遍历所有结点；
?? ( 2 ) (2) (2) 遍历到的结点，将结点的数据域带上->后输出;
?? ( 3 ) (3) (3) 将当前结点置为当前结点的后继结点，继续迭代；
?? ( 4 ) (4) (4) 最后输出一个NULL，代表一个完整的链表；

对于上面例子中的链表，调用这个函数，得到的结果为：

1 -> 3 -> 8 -> 2 -> 6 -> NULL

3、测试用例

例如，我们在头插法的实现过程中，加上一句链表的打印语句，代码实现如下：

ListNode *ListCreateListByHead(int n, int *a) {ListNode *head = NULL, *vtx; while(n--) {vtx = ListCreateNode(a[n]); vtx->next = head; head = vtx; ListPrint(head); /*看这里，看这里！*/ } return head; }

运行后得到的结果如下：

6 -> NULL 2 -> 6 -> NULL 8 -> 2 -> 6 -> NULL 3 -> 8 -> 2 -> 6 -> NULL 1 -> 3 -> 8 -> 2 -> 6 -> NULL

这样，我们就能更加进一步的确保我们实现头插法这个算法的正确性了。

验证算法的正确性有两个有效的办法：
?? ( 1 ) (1) (1) 构造大量的测试数据进行输入输出测试；
?? ( 2 ) (2) (2) 打印每一个操作后，数据结构的当前状态，看是否和预期相符；

对链表进行打印，就是利用了这里的第( 2 ) (2) (2) 点，这个方法虽然原始，但是能够让你对每一步操作都了然于胸，尤其是写到后面，代码量爆炸的时候，这个方法往往能够让你规避很多不必要的逻辑错误。

五、链表元素的索引 1、算法描述

??给定一个链表头结点head，并且给定一个索引值i ( i ≥ 0 ) i (i \ge 0) i(i≥0)，求这个链表的第i i i 个结点（为了和 C语言的数组下标保持一致，我们假定链表头结点代表第 0 个结点）。

这实际上是一个遍历链表的过程，我们先来看下动画演示。

2、动画演示

上图演示的是通过遍历，索引到第 3 个结点（下标从 0 开始计数）的过程，其中：
??head 代表链表头结点；
??tail 代表链表尾结点；
??j / temp 代表当前枚举到的第j ( j ≥ 0 ) j (j \ge 0) j(j≥0)个结点，即动图中的 橙色实心结点；

3、源码详解

ListNode *ListGetNode(ListNode *head, int i) {ListNode *temp = head; // (1) int j = 0; // (2) while(temp && j < i) { // (3) temp = temp->next; // (4) ++j; // (5) } if(!temp || j > i) {return NULL; // (6) } return temp; // (7) }

( 1 ) (1) (1) temp代表从链表头开始的游标指针，用于对链表进行遍历操作；
( 2 ) (2) (2) j代表当前访问到了第j j j 个结点；
( 3 ) (3) (3) 如果游标指针非空，并且j < i，则代表还没访问到目标结点，继续执行循环；
( 4 ) (4) (4) 将游标指针的后继结点作为新一轮的游标指针，继续迭代；
( 5 ) (5) (5) j自增，等价于j = j + 1;
( 6 ) (6) (6) 当游标指针为空，或者j > i，则说明给定的i超过了链表长度，返回空结点；
( 7 ) (7) (7) 最后，返回找到的第i个结点；

4、测试用例

void testListGetNode(ListNode *head) {int i; for(i = 0; i < 7; ++i) {ListNode *node = ListGetNode(head, i); if(!node) printf("index(%d) is out of range.\n", i); else printf("node(%d) is %d.\n", i, node->data); } } int main() {int a[5] = { 1, 3, 8, 2, 6}; ListNode *head = ListCreateListByHead(5, a); // (1) testListGetNode(head); // (2) return 0; }

这个测试用例，首先第( 1 ) (1) (1) 步，利用头插法对给定数组创建了一个链表；然后第( 2 ) (2) (2) 步，枚举i ∈ [ 0 , 6 ] i \in [0, 6] i∈[0,6]，分别去取链表的第i i i 个结点，运行结果如下：

node(0) is 1. node(1) is 3. node(2) is 8. node(3) is 2. node(4) is 6. index(5) is out of range. index(6) is out of range.

这表明当下标在链表元素个数范围内时，能够找到对应结点；否则，返回的是空节点；进一步验证了程序实现的正确性。

5、算法分析 1）时间复杂度

索引结点的操作，最坏情况下需要遍历整个链表，所以时间复杂度为O ( n ) O(n) O(n)。

2）空间复杂度

整个索引过程只记录了两个变量：游标结点和当前索引值。和链表长度无关，所以空间复杂度为O ( 1 ) O(1) O(1)。

六、链表元素的查找 1、算法描述

??给定一个链表头head，并且给定一个值v v v，查找出这个链表上数据域等于v v v 的第一个结点。

查找的过程，基本和索引类似，也是对链表的遍历操作，首先请看动画演示。

2、动画演示

上图演示的是通过遍历，查找到值为 2 的结点的过程，其中：
??head 代表链表头结点；
??tail 代表链表尾结点；
??j / temp 代表当前枚举到的第j ( j ≥ 0 ) j (j \ge 0) j(j≥0)个结点，即动图中的 橙色实心结点；

3、源码详解

ListNode *ListFindNodeByValue(ListNode *head, DataType v) {ListNode *temp = head; // (1) while(temp) { // (2) if(temp->data =https://www.it610.com/article/= v) {return temp; // (3) } temp = temp->next; // (4) } return NULL; // (5) }

( 1 ) (1) (1) temp代表从链表头开始遍历的游标指针；
( 2 ) (2) (2) 如果游标指针非空，继续循环；
( 3 ) (3) (3) 一旦发现数据域和给定的参数v相等，立即返回该结点对应的指针；
( 4 ) (4) (4) 否则，将游标指针的后继结点作为新一轮的游标指针，继续迭代；
( 5 ) (5) (5) 一直到链表尾都找不到，返回 NULL；

4、测试用例

void testListFindNodeByValue(ListNode *head) {int i; for(i = 1; i <= 6; ++i) {ListNode *node = ListFindNodeByValue(head, i); if(!node) printf("value(%d) is not found!\n", i); else printf("value(%d) is found!\n", i); } } int main() {int a[5] = { 1, 3, 8, 2, 6}; ListNode *head = ListCreateListByHead(5, a); testListFindNodeByValue(head); return 0; }

这个测试用例，就是选择了[ 1 , 6 ] [1, 6] [1,6] 这六个数，然后依次利用ListFindNodeByValue去链表中查找，运行结果如下：

value(1) is found! value(2) is found! value(3) is found! value(4) is not found! value(5) is not found! value(6) is found!

5、算法分析 1）时间复杂度

查找结点的操作，最坏情况下就是找不到，需要遍历整个链表，所以时间复杂度为O ( n ) O(n) O(n)。

2）空间复杂度

整个查找过程只记录了一个变量：游标指针。和链表长度无关，所以空间复杂度为 O(1)。

七、链表结点的插入 1、算法描述

??给定一个链表头head，并且给定一个位置i ( i ≥ 0 ) i(i \ge 0) i(i≥0) 和一个值v v v，求生成一个值为v v v 的结点，并且将它插入到链表第i i i 个结点之后。

首先，我们需要找到第i i i 个位置，可以利用上文提到的链表结点的索引；然后，再执行插入操作，而插入操作分为两步：第一步就是创建结点的过程；第二步，是断开之前第i i i 个结点和第i + 1 i+1 i+1 个结点之间的 “链”，并且将创建出来的结点 “链接” 到两者之间。来看下动图演示。

2、动画演示

上图演示的是通过遍历，将数据为 8 的结点插入到链表第 1 个（下标从 0 开始）结点后的过程，其中：
??head 代表链表头结点；
??tail 代表链表尾结点；
??pre 代表待插入结点的前驱结点，也是游标指针指代的结点，即动图中的 橙色实心结点；
??aft 代表待插入结点的后继结点，即动图中的 蓝色实心结点；
??vtx 代表将要插入的结点，即动图中的 绿色实心结点；

3、源码详解

ListNode *ListInsertNode(ListNode *head, int i, DataType v) {ListNode *pre, *vtx, *aft; // (1) int j = 0; // (2) pre = head; // (3) while(pre && j < i) { // (4) pre = pre->next; // (5) ++j; // (6) } if(!pre) {return NULL; // (7) } vtx = ListCreateNode(v); // (8) aft = pre->next; // (9) vtx->next = aft; // (10) pre->next = vtx; // (11) return vtx; // (12) }

( 1 ) (1) (1) 预先定义三个指针，当结点插入完毕后， pre -> vtx -> aft；
( 2 ) (2) (2) 定义一个计数器，当 j == i时，表明找到要插入的位置；
( 3 ) (3) (3) 从链表头结点开始迭代遍历链表；
( 4 ) (4) (4) 如果还没有到链表尾，或者没有找到插入位置则继续循环；
( 5 ) (5) (5) 将游标指针的后继结点作为新一轮的游标指针，继续迭代；
( 6 ) (6) (6) 计数器加 1；
( 7 ) (7) (7) 元素个数不足，无法找到给定位置，返回 NULL；
( 8 ) (8) (8) 创建一个值为v的孤立结点；
( 9 ) → ( 11 ) (9) \to (11) (9)→(11) 这三步就是为了将vtx插入到pre -> aft之间，插入完毕后pre -> vtx -> aft。
( 12 ) (12) (12) 最后，返回插入的那个结点；

4、测试用例

void testListInsertNode(ListNode *head) {ListPrint(head); ListInsertNode(head, 1, 8); ListPrint(head); }int main() {int a[5] = { 1, 3, 2, 6}; ListNode *head = ListCreateListByHead(4, a); testListInsertNode(head); return 0; }

这个测试用例，就是在原链表1 -> 3 -> 2 -> 6的基础上，在第 1 个结点（0 - based）的后面插入一个值为 8 的结点，并且返回这个结点。这个例子的运行结果如下：

1 -> 3 -> 2 -> 6 -> NULL 执行插入操作！ 1 -> 3 -> 8 -> 2 -> 6 -> NULL

5、算法分析 1）时间复杂度

虽然插入操作本身是O ( 1 ) O(1) O(1) 的，但是这里有一步索引结点的操作，最坏情况下就是找不到对应的结点，需要遍历整个链表，所以时间复杂度为O ( n ) O(n) O(n)。

2）空间复杂度

整个查找和插入的过程只记录了三个变量，和链表长度无关，所以空间复杂度为O ( 1 ) O(1) O(1)。

八、链表结点的删除 1、算法描述

??给定一个链表头head，并且给定一个位置i ( i ≥ 0 ) i(i \ge 0) i(i≥0)，将位置为i i i 的结点删除，并且返回新链表的头结点（为什么要返回头结点？因为被删掉的有可能是原来的头结点）。

链表结点的删除问题可以分为三种情况进行讨论，如下：

文章图片
( 1 ) (1) (1) 空链表：无法进行删除，直接返回空结点；
( 2 ) (2) (2) 非空链表删除头结点：缓存下头结点的后继结点，释放头结点内存，再返回这个后继结点；
( 3 ) (3) (3) 非空链表删除非头结点：通过遍历，找到需要删除结点的前驱结点，如果需要删除结点自身为空，则返回链表头结点；否则，缓存需要删除结点以及它的后继结点，将前驱结点指向后继结点，然后再释放需要删除结点的内存，返回链表头结点；

2、动画演示

上图演示的是通过遍历，将第 2 号结点（下标从 0 开始）删除的过程，其中：
??head 代表链表头结点；
??tail 代表链表尾结点；
??pre 代表待删除结点的前驱结点，也是游走指针指代的结点，即动图中的 橙色实心结点；
??aft 代表待删除结点的后继结点，即动图中的 绿色实心结点；
??del 代表将要删除的结点，即动图中的 红色实心结点；

3、源码详解

ListNode *ListDeleteNode(ListNode *head, int i) {ListNode *pre, *del, *aft; int j = 0; if(head == NULL) {return NULL; // (1) } if(i == 0) { // (2) del = head; // (3) head = head->next; // (4) free(del); // (5) return head; // (6) }pre = head; // (7) while(pre && j < i - 1) { // (8) pre = pre->next; ++ j; } if(!pre || !pre->next) { // (9) return head; } del = pre->next; // (10) aft = del->next; // (11) pre->next = aft; // (12) free(del); // (13) return head; // (14) }

( 1 ) (1) (1) 空链表，无法执行删除，直接返回；
( 2 ) (2) (2) 需要删除链表第 0 个结点；
( 3 ) (3) (3) 缓存第 0 个结点；
( 4 ) (4) (4) 将新的链表头结点变为当前头结点的后继结点；
( 5 ) (5) (5) 调用系统库函数free释放内存；
( 6 ) (6) (6) 返回新的链表头结点；
( 7 ) (7) (7) 从链表头结点开始遍历链表；
( 8 ) (8) (8) 找到将要被删除结点的前驱结点pre；
( 9 ) (9) (9) 如果前驱结点为空，或者需要删除的结点为空，则直接返回当前链表头结点；
( 10 ) (10) (10) 缓存需要删除的结点到del；
( 11 ) (11) (11) 缓存需要删除结点的后继结点到aft；
( 12 ) (12) (12) 将需要删除的结点的前驱结点指向它的后继结点；
( 13 ) (13) (13) 释放需要删除结点的内存空间；
( 14 ) (14) (14) 返回链表头结点；

4、测试用例

void testListDeleteNode(ListNode *head) {ListPrint(head); printf("执行 2 号结点删除操作！\n"); head = ListDeleteNode(head, 2); ListPrint(head); printf("执行 0 号结点删除操作！\n"); head = ListDeleteNode(head, 0); ListPrint(head); }int main() {int a[5] = { 1, 3, 8, 2, 6}; ListNode *head = ListCreateListByHead(5, a); // (1) testListDeleteNode(head); // (2) return 0; }

这个用例的第( 1 ) (1) (1) 步通过头插法创建了一个 1 -> 3 -> 8 -> 2 -> 6的链表，然后将 2 号结点删除，再将头结点删除，运行结果如下：

1 -> 3 -> 8 -> 2 -> 6 -> NULL 执行 2 号结点删除操作！ 1 -> 3 -> 2 -> 6 -> NULL 执行 0 号结点删除操作！ 3 -> 2 -> 6 -> NULL

5、算法分析 1）时间复杂度

删除结点本身的时间复杂度为O ( 1 ) O(1) O(1)。
但是由于需要查找到需要删除的结点，所以总的时间复杂度还是O ( n ) O(n) O(n) 的。

2）空间复杂度

不需要用到额外空间，所以总的时间复杂度为O ( 1 ) O(1) O(1)。

九、链表的销毁 1、算法描述

??链表的销毁，就是需要将所有结点的内存空间进行释放，并且需要将链表的头结点置空。

链表的销毁，可以理解成不断删除第 0 号结点的过程，直到链表头为空位置，只是一个循环调用，这里就不多做介绍，有兴趣的朋友可以自行实现一下。

2、动画演示

上图所示的是链表销毁的整个插入过程，其中：
??head 代表链表头结点，即动图中的 绿色结点，每删除一个结点，头结点就变成了之前头结点的后继结点；
??tail 代表链表尾结点；
??temp 代表待删除结点，即动图中的 橙色结点，执行删除后，它的内存空间就释放了；

3、源码详解

void ListDestroyList(ListNode **pHead) { // (1) ListNode *head = *pHead; // (2) while(head) { // (3) head = ListDeleteNode(head, 0); // (4) } *pHead = NULL; // (5) }

( 1 ) (1) (1) 这里必须用二级指针，因为删除后需要将链表头置空，普通的指针传参无法影响外部指针变量；
( 2 ) (2) (2) 给链表头结点解引用，即通过链表头结点的地址获取链表头结点；
( 3 ) (3) (3) 如果链表非空，则继续循环；
( 4 ) (4) (4) 每次迭代，删除链表头结点，并且返回其后继结点作为新的链表头结点；
( 5 ) (5) (5) 最后，将链表头结点置空，这样当函数返回时，传参的head才能是NULL，否则外部会得到一个内存已经释放了的野指针；

4、测试用例

void ListDestroyList(ListNode **pHead) {ListNode *head = *pHead; while(head) {head = ListDeleteNode(head, 0); } *pHead = NULL; } void testListDestroyList(ListNode **head) {ListPrint(*head); ListDestroyList(head); ListPrint(*head); }int main() {int a[5] = { 1, 3, 8, 2, 6}; ListNode *head = ListCreateListByHead(5, a); testListDestroyList(&head); return 0; }

测试用例主要是先创建了一个链表，然后通过不断删除链表头结点，并且打印当前链表的过程，所以运行结果中我们可以看到整个链表的删除过程，当所有结点都被删除以后，head变为NULL。

1 -> 3 -> 8 -> 2 -> 6 -> NULL 3 -> 8 -> 2 -> 6 -> NULL 8 -> 2 -> 6 -> NULL 2 -> 6 -> NULL 6 -> NULL NULL NULL

5、算法分析 1）时间复杂度

删除链表头结点的过程，每次从头部开始删除，所以时间复杂度为O ( 1 ) O(1) O(1)。
总共遍历n n n 次删除，是乘法关系，所以总的时间复杂度是O ( n ) O(n) O(n) 的。

2）空间复杂度

全程只需要一个游标指针用于遍历链表，和链表长度无关，所以总的时间复杂度为O ( 1 ) O(1) O(1)。

十、链表的优缺点 1、优点

内存分配：
??由于是链式存储，随时增加元素随时分配内存，不需要像数组那样进行预分配存储空间；
插入：
??当拥有链表某个结点的指针时，在它后继位置插入一个新的结点的的时间复杂度为O ( 1 ) O(1) O(1)；
删除：
??当拥有链表某个结点的指针时，删除它的后继结点的时间复杂度为O ( 1 ) O(1) O(1)；

2、缺点