_{王道c班级参考资料}
——
C语言部分^卷5数据结构
^_节1链表

最新版本V3.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

概述

_Gn!

在日常的工作开发中，最常用的数据结构有：数组、链表、栈、队列、哈希表和二叉搜索树。其中：

1. 数组和链表是线性数据结构的两种典型物理实现。它们是最基础的数据结构，是构成其它更复杂数据结构的基石。

   1. 数组采用一段连续的内存空间存储，最大的特点是基于索引的快速随机访问。

   2. 链表则由非连续存储的、基于指针链接的结点组成，提供了灵活的插入和删除操作。

2. 栈和队列是数组和链表的经典应用场景。它们都可以基于数组或链表实现，不同的是栈遵循先进后出的原则，而队列遵循先进先出的原则。

3. 哈希表通常结合数组与链表来实现，用于提供快速的数据查询能力。

4. 二叉搜索树是一种基于树形的数据结构，它提供了优秀的搜索效率。二叉搜索树在实现时可以借鉴链表的实现思路，所以它和链表也有一定的关联。

总之，数组和链表作为数据结构的基础，理解数组和链表对于学习其他数据结构至关重要。尤其是链表，因为它在构建复杂数据结构时扮演核心角色。

本章节中，我们就来一起学习一下链表以及基于C语言来实现链表。

如何学习数据结构

_Gn!

我们建议大家学习一种数据结构，可以从三个角度入手：

1. 理论基础与模型。学习一种数据结构，首先要做的就是理解它的概念模型以及知晓其理论基础，包括其特点、用途和适用场景等。

2. 基础操作。在掌握了基本理论后，就需要进一步熟悉该数据结构的基础操作以及这些操作的工作原理。这些基础操作一般包括：增、删、查以及遍历。(改操作是查操作的扩展)

3. 实现与应用。在了解理论和操作后，就可以编写代码来实现这些数据结构了，这不仅有助于巩固理解数据结构，同时也能提升编程能力。

那么基于以上学习方式，我们先来学习一下链表。推荐两个学习网站：

1. Visualgo可视化数据结构与算法

2. Data Structure Visualization (usfca.edu)

链表

_Gn!

链表：是一种线性数据结构，由一系列结点"链接"构成。

结点：在C语言中，一个结点通常是一个结构体对象。该结构体对象由数据域和指针域两部分组成。数据域用于存储数据，而指针域则用于存放其它结点的指针。

如下图所示(其中D代表数据域，P代表指针域)：

常见的链表主要可以分为以下几种类型：

其中循环链表的使用是比较少见的，在我们学习链表的课程中就不涉及循环链表了。循环链表在处理具有环形结构的问题时非常好用，比如约瑟夫环问题，

接下来我们先讨论最常用的单向链表和双向链表(尤其是单向链表)。

单向链表

_Gn!

单向链表是由一系列结点单向链接组成的数据结构，简称单链表。

基础概念：

1. 结点：链表中的每一个存储单元被称为结点，每个结点都包含两部分：

   1. 一部分用于存储结点的数据(数据域)

   2. 另一部分用于存储指向下一个结点的指针(指针域)。

   在C程序中一个结点，就是一个结点结构体类型的对象。

2. 头结点：某些单链表的实现中，会在第一个结点前附设一个"一般不存储数据或者存储链表长度信息"的结点，这个结点就是头结点。

   1. 头结点也叫做"哑结点"、"虚拟结点"、"哨兵结点"等。头结点的指针域指向链表的第一个结点。

   2. 在实际应用中，单链表一般不带头结点，但在需要统一链表头部操作的场景中，头结点具有"奇效"。

3. 尾结点：单链表的最后一个结点。它的指针域指向 NULL，表示链表的结束。

4. 头指针：指向链表第一个结点的指针，头指针非常重要，单链表的任何操作都是以头指针为入口的，单链表一定会有头指针。具体而言：

   1. 如果链表为空，则头指针为 NULL，是一个空指针。

   2. 如果单链表没有头结点，那么头指针就指向链表的第一个存储数据的结点。

   3. 如果单链表有头结点，那么头指针就指向该头结点。总之，头指针就指向单链表的第一个结点。

5. 尾指针：指向链表最后一个结点的指针。对于单链表而言，尾指针不是必须的，但拥有尾指针可以使得链表尾部的操作更加简单高效。

基本操作：

1. 创建链表

2. 销毁链表

3. 插入结点：对于链表而言，只要在一个确定的结点后面插入结点，都是一个基础的，时间复杂度为O(1)的操作。

   1. 在一个存在头指针和尾指针的链表当中，头插和尾插就是基础的插入结点操作。

   2. 更复杂的插入操作都是对基础插入操作的扩展，比如根据索引插入一个结点。

4. 搜索结点：链表并不支持随机访问，任何的访问操作都意味着遍历链表。

   1. 所以不管是有序无序还是搜索的条件是什么，单链表的搜索操作时间复杂度总是O(n)

   2. 比较常见的搜索条件是：根据索引查找或者根据数据查找

5. 删除结点：对于链表而言，只要是删除一个确定结点后面的一个结点，都是一个基础的，时间复杂度为O(1)的操作。

   1. 在一个存在头指针和尾指针的链表当中，删除第一个结点就是一个基础的O(1)时间复杂度操作。(但删除尾结点不是，为什么？)

   2. 如果需要删除尾结点或中间结点，则通常需要遍历链表，时间复杂度是O(n)

编写头文件

_Gn!

为了更方便的实现和使用链表，我们可以编写一个头文件(命名为linked_list.h)，来存放结构体、函数等原型。

参考代码如下：

linked_list.h头文件-参考代码

xxxxxxxxxx
47
1
// 头文件保护语法
2
#ifndef LINKED_LIST_H
3
#define LINKED_LIST_H
4

5
// 包含linked_list.h头文件也会同步包含它包含的其它头文件
6
// 根据这一特点, 可以选择将一些共用的头文件包含在此头文件中
7
#include <stdbool.h>
8
#include <stdlib.h>
9
#include <stdio.h>
10

11
typedef int DataType;
12

13
// 定义链表结点结构
14
typedef struct node {
15
    DataType data;      // 数据域
16
    struct node *next;  // 指针域
17
} Node;
18

19
// 定义链表结构本身
20
typedef struct {
21
    Node *head;     // 头指针
22
    Node *tail;     // 尾结点指针
23
    int size;       // 用于记录链表的长度
24
} LinkedList;
25

26
// 创建一个空的链表
27
LinkedList *create_linked_list();
28
// 销毁链表
29
void destroy_linked_list(LinkedList *list);
30
// 头插法
31
bool add_before_head(LinkedList *list, DataType new_data);
32
// 尾插法
33
bool add_behind_tail(LinkedList *list, DataType new_data);
34
// 根据索引插入一个新结点
35
bool add_by_idx(LinkedList *list, int idx, DataType new_data);
36
// 根据索引搜索一个结点
37
Node *search_by_idx(LinkedList *list, int idx);
38
// 根据数据搜索一个结点
39
Node *search_by_data(LinkedList *list, DataType data);
40
// 根据数据删除一个结点
41
bool delete_by_data(LinkedList *list, DataType data);
42
// 扩展: 根据索引删除一个结点
43
bool delete_by_idx(LinkedList *list, int idx);
44
// 打印单链表 格式为：1 -> 2 -> 3 ->...
45
void print_list(LinkedList *list);
46

47
#endif // !LINKED_LIST_H

基于此设计，我们可以用下图来描述我们创建的链表结构：

接下来，我们就一起来实现这个单链表。

实现链表的创建和销毁操作

_Gn!

创建一个源文件"linked_list.c"用于编码实现这个单链表。首先来实现创建和销毁两个操作，参考代码如下：

实现链表的创建和销毁操作-参考代码

xxxxxxxxxx
17
1
// 创建一个空的链表
2
LinkedList *create_linked_list() {
3
    // 使用calloc可以自动初始化成员为默认零值,更加省事
4
    return calloc(1, sizeof(LinkedList));
5
}
6
// 销毁链表
7
void destroy_linked_list(LinkedList *list) {
8
    // 遍历逐一释放结点
9
    Node *curr = list->head;
10
    while (curr != NULL) {
11
        Node *temp = curr->next;
12
        free(curr);
13
        curr = temp;
14
    }   // while循环结束时，curr指针指向NULL
15
    // 最后释放链表结构
16
    free(list);
17
}

稍微需要注意的就是销毁链表时，需要先遍历销毁所有结点才能销毁链表结构，否则会导致内存泄漏。

遍历链表一般采取固定的做法，标准范式，惯用法。如下：

1. 创建一个current结点指针指向第一个结点

2. 使用一个while循环遍历链表，通常循环的条件是"(current != NULL)"。当然也可以根据实际情况，决定循环的结束条件。

3. 在循环体中处理循环的逻辑，并在最后将current指向下一个结点。

实现打印链表

_Gn!

当你学会链表的遍历操作后，那么打印链表的操作就很容易实现了。参考代码如下：

打印单链表-参考代码

xxxxxxxxxx
14
1
// 打印单链表 格式为：1 -> 2 -> 3 ->...
2
void print_list(LinkedList *list) {
3
    Node *curr = list->head;
4
    // 遍历此单链表
5
    while (curr != NULL) {
6
        printf("%d", curr->data);
7
        // 如果不是链表的最后一个结点，就打印箭头
8
        if (curr->next != NULL) {
9
            printf(" -> ");
10
        }
11
        curr = curr->next;
12
    }
13
    printf("\n");
14
}

只需要记住最后一个结点不需要打印->符号就可以了。

实现头插法插入结点

_Gn!

头插法实现链表插入的逻辑，我们之前就讲过了。无非就是以下三步：

1. 先创建一个新结点

2. 初始化新结点：

   1. 给数据域赋值

   2. 新结点的指针域应该指向原本的第一个结点

3. 更新链表的结构信息：

   1. 头指针指向新结点

   2. 尾结点指针若是一个空指针(意味着以前的链表是一个空链表)，那么尾结点指针应该指向新结点

   3. 链表长度增加1

参考代码如下：

实现头插法插入-参考代码

xxxxxxxxxx
24
1
// 头插法
2
bool add_before_head(LinkedList *list, DataType new_data) {
3
    // 1.分配一个新结点
4
    Node *new_node = (Node *)malloc(sizeof(Node));
5
    if (new_node == NULL) {
6
        printf("malloc failed in add_before_head.\n");
7
        return false;
8
    }
9

10
    // 2.初始化这个新结点
11
    new_node->data = new_data;
12
    new_node->next = list->head;    // 新结点指向原本的第一个结点
13

14
    // 3.更新头指针指向新结点
15
    list->head = new_node;  // 新结点成为第一个结点
16

17
    // 4.如果尾结点指针是NULL，说明链表头插前为空，那么新结点同时成为尾结点
18
    // 需要更新尾结点指针
19
    if (list->tail == NULL) {
20
        list->tail = new_node;
21
    }
22
    list->size++;
23
    return true;
24
}

稍微需要注意的是：

由于链表结构体中存储了指向尾结点的尾结点指针，所以在有必要的情况下，也要更新这个尾结点指针。

实现尾插法插入结点

_Gn!

尾插法也就是将一个新结点插入到链表的末尾，成为新的尾结点。具体而言，它的逻辑也可以三步实现：

1. 先创建一个新结点

2. 初始化新结点：

   1. 给数据域赋值

   2. 新结点的指针域应该指向NULL(因为新结点要成为新的尾结点)

3. 更新链表的结构信息：

   1. 若以前的链表为空，那么头指针也应该指向新结点。

   2. 若以前的链表非空，则头指针不用更新。只需要将以前尾结点指针指向的结点，指向新结点。(以前的尾结点成为现在的倒数第二个结点)

   3. 将链表的尾结点指针指向新结点。

   4. 链表长度增加1

参考代码如下：

实现尾插法插入-参考代码

xxxxxxxxxx
28
1
// 尾插法
2
bool add_behind_tail(LinkedList *list, DataType new_data) {
3
    // 1.分配一个新结点
4
    Node *new_node = malloc(sizeof(Node));
5
    if (new_node == NULL) {
6
        printf("malloc failed in add_behind_tail.\n");
7
        return false;
8
    }
9

10
    // 2.初始化新结点的指针域和数据域，指针域初始为NULL
11
    new_node->data = new_data;
12
    new_node->next = NULL;
13

14
    // 3.如果尾结点指针是NULL，说明链表尾插前为空，那么新结点同时成为第一个结点和尾结点
15
    if (list->tail == NULL) {
16
        // 链表为空
17
        list->head = new_node;
18
        list->tail = new_node;
19
        list->size++;
20
        return true;
21
    }
22

23
    // 4.如果尾指针不是NULL，让以前的尾结点指向新结点，然后更新尾指针
24
    list->tail->next = new_node;
25
    list->tail = new_node;
26
    list->size++;
27
    return true;
28
}

实现根据索引插入结点

_Gn!

链表本身是没有内置索引机制的，当我们提到"链表的索引"，实际上只是人为的给链表的所有结点编个号：

1. 从第一个结点开始编号，索引是0

2. 第二个结点索引是1

3. ...

4. 链表的尾结点，索引就是长度-1

所以基于索引对链表进行插入，也就是一种基于链表结点位置的插入方式罢了。其逻辑仍然可以三步来完成：

1. 参数校验。代表要插入位置的，索引取值范围应该是[0, 链表长度]，其中：

   1. 索引取0代表头插法插入元素

2. 索引取链表长度代表尾插法插入元素

3. 取中间值时，需要遍历链表查找位置后再插入。

4. 其余索引取值都是不合法的。

5. 边界值处理。如上所示，索引取值为0和链表长度时，就代表头插和尾插，直接调用已实现的两个函数即可。

6. 处理中间插入结点的情况。

   1. 创建一个新结点，并将其数据部分设置为要插入的数据。

7. 使用一个current结点指针遍历链表，找到目标索引的前一个结点。(在链表中间插入结点时，由于单链表的结点指针域只记录下一个结点，所以必须找到前一个结点才能插入下一个位置)

8. 将新结点的指针指向current结点的下一个结点。

9. 将current结点的指针指向新结点。

10. 更新链表长度。

参考代码如下：

实现索引插入-参考代码

xxxxxxxxxx
39
1
// 根据索引插入一个新结点
2
bool add_by_idx(LinkedList *list, int idx, DataType new_data) {
3
    // 1.参数校验,避免传入不合法的索引
4
    if (idx < 0 || idx > list->size) {
5
        printf("Illegal Argument: index %d out of bouns in add_node_by_idx.\n", idx);
6
        return false;
7
    }
8
    // 2.边界值处理, 即处理头插和尾插的情况
9
    if (idx == 0) {
10
        return add_before_head(list, new_data);
11
    }
12
    if (idx == list->size) {
13
        return add_behind_tail(list, new_data);
14
    }
15
    // 3.处理在中间插入结点的情况
16
    // 3.1分配新结点, 并初始化数据域
17
    Node *new_node = malloc(sizeof(Node));
18
    if (new_node == NULL) {
19
        // 内存分配失败处理
20
        printf("malloc failed in add_index.\n");
21
        return false;
22
    }
23
    new_node->data = new_data;
24

25
    // 3.2遍历找到目标索引的前一个结点
26
    Node *prev = list->head;
27
    for (int i = 0; i < idx - 1; i++) {
28
        prev = prev->next;
29
    }       // 循环结束后, prev指针指向idx索引前面的一个结点
30

31
    // 3.3在idx位置, 插入新结点. 
32
    // 该过程先让新结点指向prev的后继结点, 再让prev结点指向新结点
33
    new_node->next = prev->next;
34
    prev->next = new_node;
35

36
    // 4.更新size
37
    list->size++;
38
    return true;
39
}

这段代码中，尤其需要思考的是for循环遍历的条件，也就是"i < index - 1"。如果不理解，可以画图思考一下。

实现根据索引搜索结点

_Gn!

在实现删除操作之前，我们先来实现两个搜索的操作。

根据索引搜索结点，这个操作其实非常类似上面根据索引查找元素，但还是稍有区别：

1. 参数校验的条件要改变。由于此时的索引不再是插入的位置，而是搜索已存在的结点。所以索引不能再取到"list -> size"链表长度了。

2. 返回值不再是bool类型，而是结点指针类型。所以失败时返回NULL。

3. 在上面一个函数当中，我们要查找的是目标索引的前一个结点，但此时我们就要查找目标索引结点。所以for循环的条件要改为"i < index"。

参考代码如下：

实现根据索引搜索结点-参考代码

xxxxxxxxxx
14
1
// 根据索引搜索一个结点
2
Node *search_by_idx(LinkedList *list, int idx) {
3
    // 1.参数校验,避免传入不合法的索引
4
    if (idx < 0 || idx > list->size - 1) {
5
        printf("Illegal Argument: index %d out of bouns in search_by_index.\n", idx);
6
        return NULL;
7
    }
8
    // 2.遍历找到目标索引的结点, 注意循环的条件
9
    Node *curr = list->head;
10
    for (int i = 0; i < idx; i++) {
11
        curr = curr->next;
12
    }   // while循环结束时, curr指针就指向idx位置的结点
13
    return curr;
14
}

实现根据数据搜索结点

_Gn!

根据数据搜索结点也非常简单，只需要在遍历链表的循环当中判断即可，这是我们已经比较熟悉的操作了。

参考代码如下：

实现根据数据搜索结点

xxxxxxxxxx
13
1
// 根据数据搜索一个结点
2
Node *search_by_data(LinkedList *list, DataType data) {
3
    Node *curr = list->head;
4
    while (curr != NULL) {
5
        if (curr->data == data) {
6
            // 找到目标结点，返回该结点
7
            return curr;
8
        }
9
        curr = curr->next;
10
    }
11
    // 遍历完整条链表都没找到, 说明目标结点不存在
12
    return NULL;
13
}

实现根据数据删除结点

_Gn!

删除操作是所有操作中，相对最复杂的，所以我们放在最后再讲。

第一种情况，若删除的结点是链表第一个结点，如下图所示：

也就是说该函数的实现逻辑第一部分是：

1. 初始化一个current指针，指向链表的第一个结点，该指针用于遍历整个链表。

2. 判断被删除的结点是否是第一个结点，如果要删除的结点是第一个结点：

   1. 更新头指针，头指针指向current结点的下一个结点。

   2. 若头指针更新后指向NULL，说明链表仅有一个结点，则需要更新尾结点指针也指向NULL

3. 释放被删除结点的内存空间。

4. 链表长度减1

这部分逻辑的参考代码如下：

实现根据数据删除结点-参考代码1

xxxxxxxxxx
18
1
// 根据数据删除一个结点
2
bool delete_by_data(LinkedList *list, DataType data) {
3
    // 定义一个临时指针用于遍历链表
4
    Node *curr = list->head;
5
    // 如果要删除的结点是第一个结点,则需要更新头指针
6
    if (curr->data == data) {
7
        list->head = curr->next;
8
        // 如果链表仅有一个结点，则更新尾结点指针
9
        if (list->head == NULL) {
10
            list->tail = NULL;
11
        }
12
        // 释放此结点空间
13
        free(curr);
14
        list->size--;
15
        return true;
16
    }
17
    // 如果要删除的结点，不是第一个结点
18
}

判断删除第一个结点完成后，我们可以完成第二部分逻辑——删除非第一个结点的其它结点。

其删除的逻辑可以用下图表示：

此逻辑的核心就是：由于单链表每个结点仅包含指向下一个结点的指针，没有指向前驱结点的指针。所以在删除中间某个结点时，为了避免链表"断开"，必须记录被删除结点的前一个结点以能够重新链接整个链表。(也就是图中的before指针)

具体的逻辑是：

1. 初始化一个before指针，指向链表的第一个结点，该指针用于记录被遍历结点的前一个结点。

2. current指针指向链表的第二个结点，开始从第二个结点遍历链表。

3. 在遍历中判断结点是不是要删除的结点，如果没有找到就一直遍历下去。

4. 如果找到目标结点：

   1. 将before结点指向current结点的下一个结点。

   2. 如果current结点的下一个结点是NULL，说明要删除的是尾结点，于是将tail指针指向before结点

   3. 释放current结点

   4. 链表的长度减1

5. 如果遍历整个链表都没有找到目标结点，说明目标结点不存在，可以直接返回false。

整个函数的参考代码如下：

实现根据数据删除结点-完整参考代码

xxxxxxxxxx
40
1
// 根据数据删除一个结点
2
bool delete_by_data(LinkedList *list, DataType data) {
3
    // 定义一个临时指针用于遍历链表
4
    Node *curr = list->head;
5
    // 如果要删除的结点是第一个结点,则需要更新头指针
6
    if (curr->data == data) {
7
        list->head = curr->next;
8
        // 如果链表仅有一个结点，则更新尾结点指针
9
        if (list->head == NULL) {
10
            list->tail = NULL;
11
        }
12
        // 释放此结点空间
13
        free(curr);
14
        list->size--;
15
        return true;
16
    }
17

18
    // 如果要删除的不是第一个结点, 则从第二个结点开始遍历查找待删除目标结点
19
    // 删除操作需要两个指针完成: curr指针用于查找待删除目标结点, prev指向待删除结点的前驱结点
20
    Node *prev = curr;  // prev始终指向curr结点的前驱
21
    curr = curr->next;  // curr指针用于遍历查找待删除的结点
22
    while (curr != NULL) {
23
        if (curr->data == data) {   // 找到目标结点,开始删除操作
24
            prev->next = curr->next;    // 核心操作: 让待删除结点的前驱结点指向待删除结点的后继, 这样待删除结点就被绕过去了
25
            if (curr->next == NULL) {
26
                // 待删除的是尾结点
27
                list->tail = prev;
28
            }
29
            // 释放被删除结点空间
30
            free(curr);
31
            list->size--;
32
            return true;
33
        }
34
        // 当前结点不是待删除目标结点,继续遍历
35
        prev = curr;
36
        curr = curr->next;
37
    }
38
    // 遍历完都未找到目标结点, 删除失败
39
    return false;
40
}

以上。

_Rd!

思考一个问题：

我们利用用链表的head指针删除头结点，时间复杂度是O(1)。

而上述代码在删除尾结点时，由于需要遍历整个链表，时间复杂度是O(n)，但实际上链表中也有一个指向尾结点的指针tail，那么利用这个tail指针，可以把删除尾结点的操作时间复杂度优化到O(1)吗？为什么？

扩展: 根据索引删除结点

_Gn!

你已经理解了根据结点取值删除某个结点，那么根据索引删除结点就更简单了。思路大体如下：

1. 仍然需要先检查一下索引是否合法，由于是搜索，所以索引合法的区间范围是[0, size-1]

2. 仍然需要两个指针来完成结点的删除操作

3. 第一个结点的删除仍然可以做特殊处理，后续结点则可以通过遍历找到它以及它的前驱后删除。

4. 删除第一个结点和尾结点时，需要更新头指针和尾指针

整个函数的参考代码如下：

根据索引删除结点-参考代码

xxxxxxxxxx
41
1
// 扩展: 根据索引删除结点
2
bool delete_by_idx(LinkedList *list, int idx) {
3
    // 检查待搜索的索引是否越界，索引的合法范围是[0, size-1]
4
    if (idx < 0 || idx >= list->size) {
5
        printf("Illegal Arguments: index = %d\n", idx);
6
        return false;
7
    }
8

9
    // 同样需要两个指针来完成结点的删除
10
    Node *curr = list->head;
11
    Node *prev = NULL;
12

13
    // 如果要删除的是第一个结点
14
    if (idx == 0) {
15
        list->head = curr->next;  // 更新头指针
16
        // 若删除的结点是唯一的结点
17
        if (list->size == 1) {
18
            list->tail = NULL;  // 更新尾指针
19
        }
20
        free(curr);
21
        list->size--;
22
        return true;
23
    }
24

25
    // 如果删除的结点不是第一个结点
26
    for (int i = 0; i < idx; i++) {
27
        prev = curr;
28
        curr = curr->next;
29
    }
30

31
    // 核心操作: 让前驱结点指向后继结点
32
    prev->next = curr->next;
33

34
    // 如果要删除的是尾结点, 则需要更新尾指针
35
    if (idx == list->size - 1) {
36
        list->tail = prev;
37
    }
38
    free(curr);
39
    list->size--;
40
    return true;
41
}

以上。

测试用例

_Gn!

虽然单链表测试非常简单，但还是给出一个测试用例：

测试用例-参考代码

xxxxxxxxxx
47
1
int main(void) {
2
    // 创建一个空的链表
3
    LinkedList *list = create_linked_list();
4

5
    // 测试头部插入
6
    add_before_head(list, 10);
7
    add_before_head(list, 20);
8
    add_before_head(list, 30);
9

10
    printf("在头部插入30, 20, 10后:\n");
11
    print_list(list); // 预期输出: 30 -> 20 -> 10
12

13
    // 测试尾部插入
14
    add_behind_tail(list, 40);
15
    add_behind_tail(list, 50);
16

17
    printf("在尾部插入40, 50后:\n");
18
    print_list(list); // 预期输出: 30 -> 20 -> 10 -> 40 -> 50
19

20
    // 测试按索引插入
21
    add_by_idx(list, 2, 25); // 在索引2的位置插入25
22

23
    printf("在索引2插入25后:\n");
24
    print_list(list); // 预期输出: 30 -> 20 -> 25 -> 10 -> 40 -> 50
25

26
    // 测试按索引搜索
27
    Node *node = search_by_idx(list, 2);
28
    printf("索引2处的元素: %d\n", node->data); // 预期输出: 25
29

30
    // 测试按数据搜索
31
    node = search_by_data(list, 40);
32
    printf("找到数据40的结点: %d\n", node->data); // 预期输出: 40
33

34
    // 测试按数据删除
35
    delete_by_data(list, 25);
36
    printf("删除数据25后:\n");
37
    print_list(list); // 预期输出: 30 -> 20 -> 10 -> 40 -> 50
38

39
    // 测试按索引删除
40
    delete_by_idx(list, 0); // 删除索引0处的元素
41
    printf("删除索引0处的元素后:\n");
42
    print_list(list); // 预期输出: 20 -> 10 -> 40 -> 50
43

44
    // 销毁链表
45
    destroy_linked_list(list);
46
    return 0;
47
}

以上。

总结

_Gn!

至此，我们已经基于C语言实现了一个单链表。这里我们可以比较一下链表的各种操作的效率：

1. 插入操作：

2. 如果采用头插或尾插，时间复杂度是O(1)

3. 如果依据索引在链表中间插入一个结点，往往需要遍历链表，时间复杂度是O(n)

4. 删除操作

   1. 如果删除的是第一个结点，时间复杂度是O(1)

   2. 如果删除的不是第一个结点甚至被删除的结点不存在时，就需要遍历整个链表，时间复杂度是O(n)

5. 查找操作，链表的查询（不论是根据索引还是根据数据）往往都需要遍历链表，时间复杂度是O(n)

总结：

1. 单链表在头部的操作（插入和删除）效率很高，但在尾部或中间的操作效率较低，因为这些操作通常需要遍历整个链表。

2. 如果不需要遍历操作，在一个已知结点的后面插入/删除一个结点，单链表的效率很高，时间复杂度是O(1)

3. 单链表的主要优点在于它的动态大小、更灵活的内存利用和相对于数组更简单的插入和删除操作（不需要移动大量元素）

4. 单链表的缺点在于访问元素需要遍历效率低，而且由于需要额外空间存储指针，意味着更高的内存开销。

双向链表(扩展)

_Gn!

双向链表就是在单链表的基础上，每个结点多了一个指向前一个结点的指针。如下图所示：

单向链表能够执行的操作，双向链表也都是可以的，而且时间复杂度并基本是一致的。

但在实际开发中，我们还是更倾向于使用双向链表。比如c中的list以及Java中的LinkedList这些高级语言中的链表库实现，其底层实现的数据结构都是双向链表。

原因源自于双向链表的独特魅力——它有一条指向前驱结点的链接，使得双向链表可以高效地完成一些单链表处理起来很麻烦的问题。

最典型的场景有：

1. 在一个确定的结点附近（无论前后）进行结点的新增以及删除，时间复杂复杂度都是O(1)。这是由于结点存在指向前驱和后驱结点的指针，可以直接访问前驱后驱结点。

2. 在查询操作时：

   1. 如果按照索引查询，双向链表可以根据目标索引结点接近于头部还是尾部，选择从最近的一端开始查询。尤其是当索引元素接近链表的末尾时，双向链表可以直接从尾部开始遍历元素，相比较于单链表效率提升明显。

   2. 如果按照值查询，且链表无序，那么双向链表和单链表没有什么区别。但如果双向链表是有序的，可以执行一些优化，在进行查找操作时，保留上次查找到结点的地址，以稍微提高下一次查找的效率。

   3. 总得来说，链表（无论是单向还是双向）在查询操作上的效率都是差不多的，双向链表在某些情况下可以优化一些性能，但它们访问操作的时间复杂度都是O(n)。

最后总结一下：

双向链表占用的内存空间比单链表更多，因为每个结点都包含两个指针（前驱和后继）。但尽管如此，双向链表在性能上的强大、操作上的便利也使得它特别常用。双向链表是典型的空间换时间思想的应用。

特别是在需要频繁进行双向遍历和结点的插入删除操作时，双向链表是比较有优势的。

链表面试题举例讲解

_Gn!

链表作为最基础的、灵活的常用数据结构，经常出现在各种面试问题当中，下面举例讲解一些常见的链表面试题。

下面的所有题目都基于一个链表结点的结构体类型定义：

链表结点结构体类型定义-代码

xxxxxxxxxx
4
1
typedef struct node {
2
    int data;
3
    struct node* next;
4
} Node;

我们可以直接在main函数中声明Node* head作为头指针，代指整条链表，head是NULL就表示链表为空。

实现尾插法

_Gn!

在前面讲解二级指针时，我们已经基于head头指针实现了头插法插入结点，那么现在请使用尾插法来创建链表。

首先，仍然需要使用二级指针，因为你需要修改head指针的指向。除此之外，尾插法还比头插法稍微麻烦一点——需要判断一下链表是否为空，即head指针是否为NULL：

1. 如果链表为空，尾插法就是头插法，新结点成为第一个结点。

2. 如果链表不为空，则需要遍历找到链表最后一个结点，然后再进行尾插。

总之，参考代码如下：

实现尾插法-参考代码

xxxxxxxxxx
22
1
// 尾插法
2
void insert_tail(Node** head, int val) {
3
    Node* new_node = calloc(1, sizeof(Node));   // 用calloc避免忘记设置next域为NULL！！！
4
    if (new_node == NULL) {
5
        printf("malloc failed in insert_tail.\n");
6
        exit(1);
7
    }
8
    new_node->data = val;
9
    // 尾插法要首先判断链表是否为空
10
    if (*head == NULL) {
11
        // 链表为空，那么头指针就指向新结点
12
        *head = new_node;
13
    }
14
    else {
15
        // 链表不为空，就遍历链表找到最后一个结点
16
        Node* curr = *head;
17
        while (curr->next != NULL) {
18
            curr = curr->next;
19
        }
20
        curr->next = new_node;
21
    }
22
}

特别需要注意的是，不要忘记设置结点的next域为空指针，尤其在使用malloc函数时。若忘记设置，将产生野指针，未定义行为。

求链表中间结点的值

_Gn!

给定一个链表，请编写函数求出链表中间结点的值。此函数的声明如下：

xxxxxxxxxx
1
1
int find_mid_ele(Node *head);

举例：

输入: 1 --> 2 --> 3

输出: 2

输入: 1 --> 2 --> 3 --> 4

输出: 3

该怎么办呢？

遍历链表取中间索引并求值

_Gn!

一个非常容易想到的思路就是——"先遍历整条链表，求出链表总长度，然后计算取中间索引再遍历访问"。

稍微需要注意的是，如何计算链表的中间索引。通过给出的例子，我们发现只需要求出长度，直接除以整数２就可以了。

这种思路的参考代码如下：

遍历链表取中间索引－参考代码

xxxxxxxxxx
17
1
int  find_mid_ele(const Node* head) {
2
 int len = 0;
3
 Node* current = head;
4
 // 第一次遍历链表，计算链表长度
5
 while (current != NULL) {
6
     len++;
7
     current = current->next;
8
 }
9
 // 计算中间索引，直接除以整数2就行
10
 int mid = len / 2;
11
 current = head;
12
 // 再遍历一次到mid索引位置
13
 for (int i = 0; i < mid; i++) {
14
     current = current->next;
15
 }
16
 return current->data; // 返回中间节点的值
17
}

这个思路是比较简单的，效率也不差，时间复杂度是O(n)，不占用额外内存空间空间复杂度是O(1)，但我们仍然还有一个更优的思路。

快慢指针法

_Gn!

上面的实现，遍历了1.5次整条链表，但一次遍历就已经足够找到链表的中间结点了，那么能不能把遍历次数优化到1次内呢？

快慢指针法就是用来在链表中解决这类问题的技巧之一，它通常用于找到链表的中间节点。

它的思路是这样的：

1. 初始化两个指针slow和fast都指向链表头部。

2. 下面开始遍历链表，每一次遍历移动fast指针两步，slow指针则只移动一步

3. fast指针移动到链表末尾，则恰好slow指针指向链表的中间结点。

实现的参考代码如下：

快慢指针法求中间结点-参考代码

xxxxxxxxxx
25
1
int slow_fast_find_mid_ele(const Node* head) {
2
    if (head == NULL){
3
        printf("error: list is null.\n");
4
        exit(1);
5
    }
6
    // 快慢指针都指向链表第一个结点
7
    Node* slow = head, * fast = head;
8
    /*
9
    * 遍历链表停止的条件应该是快指针到达链表的末尾
10
    * 那么如何判断快指针到达了末尾？
11
    * 有两种可能：
12
    * 1.当链表是奇数长度时，fast指针指向的结点的next域是空指针
13
    * 2.当链表是偶数长度时，fast指针本身指向的结点是空指针
14
    * 
15
    * 由于我们事先不知道链表的长度, 但链表长度不可能既是偶数又是奇数, 所以只要上述情况出现一种就表示快指针遍历完了链表
16
    * 反之, 只要没有出现上述两种情况任何一种, 那么快指针就还没有遍历完整条链表
17
    * 于是我们就可以写出下列while循环
18
    */
19
    while (fast != NULL && fast->next != NULL) {
20
        slow = slow->next;      // 慢指针前进一步
21
        fast = fast->next->next; // 快指针前进两步
22
    }
23
    // 慢指针现在指向中间节点
24
    return slow->data;
25
}

两种方式虽然都是遍历数组，时间复杂度都是O(n)，空间复杂度都是O(1)。但很明显，快慢指针法，1次遍历链表就找到了中间结点，效率会更高一些。

快慢指针法是解决链表问题，求中间结点的一个惯用法，大家要掌握它。

判断单链表是否有环

_Gn!

给出一个单链表，请判断它是否有环。

有环的意思是，它的尾结点的next域是否指向了任意其它结点，比如：

1. 尾结点next域指向第一个结点，这就是单向循环链表。

2. 尾结点next域指向链表中间任意一个结点，这就是有环。

3. 尾结点next域指向自身结点，这也是有环。

注意：单链表的结点只有一个next指针域，所以不存在除尾结点外的结点有环的情况。

该函数的声明如下：

xxxxxxxxxx
1
1
bool has_circle(Node* head);

如何实现呢？

遍历统计出现次数法

_Gn!

单链表有环意味着，如果以 curr == NULL 作为遍历单链表的结束条件，就会陷入死循环。在遍历过程中，程序会不断地重复遍历环中的结点。

于是我们就很容易想到一个解决办法思路——遍历统计出现次数法。

一个常见的解决思路是通过统计结点出现的次数来判断单链表是否有环。在遍历单链表时，将每个结点的出现次数存储起来。当再次访问到已经出现过的结点时，就可以判断单链表存在环。

这个思路简单易行，但最关键的问题是：如何存储链表结点出现的次数呢？

你可能立刻就想到了数组，但数组显然不是什么好主意：

1. 如果用数组来存储链表结点出现的次数，那么数组至少要和链表一样长。那到底是多长呢？先遍历一次链表确定然后动态分配数组？亦或者直接使用动态数组？这样操作的效率是比较低的。

2. 当然更关键的是：我们的目的是快速判断容器中的元素是否重复，有重复元素就有环，所以需要容器能够快速进行单一元素校验。数组要想执行这个操作，需要遍历整个数组，效率显然也不太高。

实际上，在这样的场景下，哈希表则是更好的选择，因为它可以实现动态扩容，并且哈希表最大的优势在于其能够快速进行插入和查找操作。因此，使用哈希表存储链表结点出现的次数，可以有效且较高效地判断单链表是否有环。

但C语言没有提供一个哈希表的库实现，必须要自己手动实现一个哈希表。

哈希表是后续课程的内容，我们这里不妨先给一段"假装已经实现哈希表"的伪代码，给大家演示一下这个思路：

利用哈希表判断单链表有环-演示伪代码

xxxxxxxxxx
16
1
#include <stdbool.h>
2
#include "hash_map.h"  // 假装这是自己实现的哈希表的头文件
3

4
// 我们设计一个只存储"结点指针(地址)"，也就是只存储key值不存储value值的哈希表
5
bool has_circle(Node* head) {
6
    HashMap* map = hashmap_create(); // 创建哈希表
7
    Node* curr = head;      // 遍历单链表将每一个结点地址存入哈希表
8
    while (curr != NULL) {
9
        if (hashmap_contains(map, curr)) {  // 如果哈希表中已存在此结点，返回true
10
            return true;    // 发现重复结点说明有环
11
        }
12
        hashmap_put(map, curr); // 将当前结点地址存入哈希表
13
        curr = curr->next; // 移动到下一个结点
14
    }
15
    return false; // 遍历结束，说明没有环
16
}

利用哈希表求解这个问题的关键点在于如何手动实现一个哈希表，但这也并不困难，后续课程会给大家讲解。

最后我们来分析一下这种求解方式：

1. 时间复杂度是O(n)，虽然哈希表的查询和插入操作平均时间复杂度都是O(1)级别，但由于整个过程需要遍历链表，总体时间复杂度是O(n)

2. 空间复杂度是O(n)，占用了额外的哈希表内存空间，哈希表的长度和链表是一样的。

这种方法求解哈希表有环问题，逻辑简单，代码简洁，虽然需要占用额外哈希表的内存空间，但仍然是一个高效可行的实现方式。

快慢指针法

_Gn!

如果链表很长，那么时间、空间复杂度O(n)的哈希表存储法就不够好用了。此时我们还是可以使用快慢指针法来求解这个问题。

基本的思路依旧是循环遍历该链表：

1. 如果快指针能够达到链表的末尾，那就意味着链表没环，结束循环。快指针到达末尾的条件是：

   1. fast指针本身是一个空指针(链表长度是一个偶数时)

   2. fast->next是一个空指针(链表长度是一个奇数时)

2. 如果链表有环，那么快指针就无法到达链表末尾，并且一定会和慢指针在环内相遇。所以只需要判断fast == slow，即可断定有环，结束循环。

具体的参考代码如下：

快慢指针法判断有环-参考代码

xxxxxxxxxx
13
1
bool has_circle(Node* head) {
2
    Node* slow = head, * fast = head;
3
    while (fast != NULL && fast->next != NULL) {
4
        slow = slow->next;          // 慢指针每次前进一步
5
        fast = fast->next->next;    // 快指针每次前进两步
6
        if (slow == fast) {
7
            // 快慢指针只要可以相遇，就表示链表有环
8
            return true;
9
        }
10
    }
11
    // 如果循环能结束，表示快指针到达链表末尾，即链表没有环
12
    return false;
13
}

这种方式求解单链表有环，比哈希表求解在性能上是更好的。

时间复杂度是：O(n)

但不占用额外内存空间，空间复杂度是O(1)

我们可以在一个普通链表的基础上，手动创建一个带环的链表，参考代码如下：

构建一个有环单链表-参考代码

xxxxxxxxxx
16
1
// 在上述链表的基础上，手动制造一个有环的链表
2
// 比如将最后一个结点的next指向第三个结点
3
Node* curr = head;
4
int count = 0;
5
Node* third = NULL;
6
while (curr->next != NULL){
7
    count++;
8
    if (count == 3){
9
        // curr现在指向第三个结点
10
        third = curr;
11
    }
12
    curr = curr->next;  
13
}   // 循环结束时,curr指针就指向最后一个结点
14

15
// 最后一个结点指向第三个结点
16
curr->next = third;

以上。

单向链表反转

_Gn!

给定一条单链表，请反转这条单链表。

举例：

输入: 1 --> 2 --> 3

输出: 3 --> 2 --> 1

由于索引的存在，反转数组是一个很简单的操作，那么反转单链表呢？怎么做？

首先该函数的声明如下：

xxxxxxxxxx
1
1
Node* reverse(Node *list);      // 反转当前单链表并返回新的头指针

循环迭代反转法

_Gn!

一个比较容易思考、理解的方法是利用循环迭代，从头到尾反转整条链表。大致思路是：

1. 从头到尾遍历整条链表，利用一个指针记录被反转结点的前驱结点。

2. 在这个过程中修改当前结点的指针域，让它指向其前驱结点。

3. 当然这个过程中，还需要一个临时指针用于记录当前结点的下一个结点，避免链表断开。

最终循环结束时，curr是一个空指针，prev则到达原本链表的尾结点，即反转后的第一个结点。

这种方式的参考实现代码如下：

循环迭代反转法-参考代码

x
1
// 循环迭代反转单链表
2
Node* reverse(Node* head) {
3
    Node* prev = NULL;  // 前一个节点指针，初始化为 NULL
4
    Node* curr = head;  // 当前节点指针，从头节点开始
5
    Node* succ = NULL;  // 后继节点指针，用于临时存储 curr 的下一个节点
6

7
    // 遍历链表直到当前节点为空
8
    while (curr != NULL) {
9
        succ = curr->next;  // 保存当前节点的下一个节点
10
        curr->next = prev;  // 反转当前节点的指针
11
        prev = curr;        // 前进 prev 和 curr 指针
12
        curr = succ;
13
    }
14

15
    // 当 curr 为 NULL 时，prev 指向新的头节点
16
    return prev;
17
}
18

19
// 可以考虑把succ指针定义在while循环内部，这样每次循环都会自动succ指针
20
Node* reverse2(Node* head) {
21
    Node* prev = NULL;  // 记录待反转的结点的前驱结点
22
    Node* current = head;   // 用于指向需要反转的链表结点
23

24
    while (current != NULL) {   // 遍历整条链表，反转整条链表
25
        Node* succ = current->next; // 临时保存当前节点的下一个节点
26
        current->next = prev;       // 反转核心逻辑代码: 使得当前结点指向它的前驱结点
27
        prev = current;             // 移动prev到当前节点
28
        current = succ;             // 继续反转下一个结点
29
    }       // 循环结束时curr是一个空指针，prev指向原本链表的尾结点，也就是新链表的第一个结点
30
    return prev;    // prev就是反转后新链表的头指针
31
}

分析：

时间复杂度：遍历整条链表，O(n)

空间复杂度：不占用额外内存空间，O(1)

递归反转链表

_Gn!

链表反转还可以使用递归来实现，是一种性能不太好但很优雅很有趣的办法。

递归的核心思想是分解大问题成更小的子问题(递归体)，直到问题足够小可以直接直接求解(递归出口)，再合并小问题得到大规模问题的解。

于是，我们就可以把"反转长度为N的链表"这个问题进行分解：

"反转长度为N的链表" = 反转头指针指向的链表第一个结点 + "反转长度为N - 1的链表"（递归体）

这个分解不会无休止进行，当：

链表头指针等于NULL(链表为空)或者链表头指针指向NULL（链表只有一个结点）时，自身就是反转，无需再次反转。（递归的出口）

依据这个思路，我们很容易就能写出下列反转链表的代码：

递归反转链表-参考代码

xxxxxxxxxx
22
1
// 递归反转单链表的函数
2
Node* reverse_recursive(Node* head) {
3
    // 递归的出口，链表如果为空或者链表只有一个结点，自身就是反转，直接返回头指针
4
    if (head == NULL || head->next == NULL) {
5
        return head;
6
    }
7
    // 如果链表长度不是0或者1，就分解这个反转操作
8
    // 注意：这里要先处理剩余(n-1)长度的链表，再处理头指针指向的第一个结点，否则链表就断开了。
9
    // 注意：n-1长度的链表反转结果的头指针，就是最终n长度的链表反转得到的头指针
10
    Node* ret = reverse_recursive(head->next);  // 当前第一个结点的next结点成为n-1长度新链表的第一个结点
11

12
    // 当前第一个结点就是反转后链表的尾结点，所以需要让当前第一个结点的下一个结点指向当前第一个结点
13
    // 当前第一个结点的下一个结点：head->next
14
    // 当前第一个结点的下一个结点指向当前的第一个结点：head->next->next = head
15
    head->next->next = head;        // 反转链表的核心操作
16

17
    // 当前第一个结点就是反转后链表的尾结点，它应该指向NULL
18
    head->next = NULL;
19

20
    // 返回反转后的链表头节点
21
    return ret;
22
}

分析：

时间复杂度：

递归过程中，仍然是需要递归处理链表的所有结点，所以时间复杂度仍然是O(n)。但由于递归本身函数进栈出栈的额外消耗，递归求解总会比循环迭代求解效率要差的。尤其是在大链表的情况下。

空间复杂度：

递归的深度基本等同于链表的长度，所以空间复杂度是O(n)。

总结：

递归求解是一个有趣的方法，理解起来也不困难。但存在性能较差，栈溢出风险，额外占用空间等缺点。

所以一般来说，还是循环迭代求解更好，尤其是当链表比较长时。

合并有序链表

_Gn!

现在有两条有许的单链表，请将它们合并成一条单链表，并且要保证合并后的链表也是有序的。(要求不能额外申请堆空间)

举例：

输入：

1 --> 3 --> 5

2 --> 4 --> 6

输出：

1 --> 2 --> 3 --> 4 --> 5 --> 6

怎么实现呢？该函数的声明如下：

xxxxxxxxxx
1
1
Node* merge_lists(Node* list1, Node* list2);

递归合并有序链表

_Gn!

其实递归合并有序链表的思路，和递归求解链表逆序的思路几乎完全是一致的。

长度为N和M的两条链表，直接合并是比较难以思考和求解的，于是我们进行分解：

长度为N和M的两条有序链表进行合并 =

1. 比较两条链表第一个结点的值，将较小值的结点作为合并后链表的第一个结点。

2. +

3. "长度为(N-1) + 长度为(M)的两条链表的有序合并"或者"长度为(N) + 长度为(M - 1)的两条链表的有序合并"

即每次递归调用，都会去掉两条链表中的一个结点。

这个分解不会无休止进行，当：

两条链表中任意一条链表为空链表时，合并的结果就是另一条还有结点的链表（递归的出口）

依据这个思路，我们比较容易就可以利用递归，求解这个问题：

递归合并有序链表-演示代码

xxxxxxxxxx
28
1
// 递归合并两个有序链表的函数
2
Node* merge_lists_recursion(Node* list1, Node* list2) {
3
    // 递归出口：任意链表为空，则返回另一条链表的头指针
4
    /*if (list1 == NULL) {
5
        return list2;
6
    }
7
    if (list2 == NULL) {
8
        return list1;
9
    }*/
10
    if (!list1 || !list2) {
11
        return list1 ? list1 : list2;
12
    }
13
    // 递归体
14
    // 分解： 
15
    // 1.比较两条链表的第一个结点的值，将较小值结点作为合并后的第一个结点(也就是最终返回值)
16
    // 2.如果list1的第一个结点值小
17
    // 那么它的next指针将指向(size1-1)长度的list1链表和size2长度的list2链表合并的结果
18
    // 3.如果list1的第一个结点值大或相等
19
    // 那么list2的next指针将指向(size1)长度的list1链表和(size2-1)长度的list2链表合并的结果
20
    if (list1->data < list2->data) {
21
        list1->next = merge_lists_recursion(list1->next, list2);
22
        return list1;
23
    }
24
    else {
25
        list2->next = merge_lists_recursion(list1, list2->next);
26
        return list2;
27
    }
28
}

当然，这个过程的逻辑还是需要认真仔细的思考一番的。

分析：

时间复杂度：O(n + m)，其中n和m分别是两个链表的长度。这是由于每次递归调用处理1个结点的合并，那么递归就需要进行n + m次。

空间复杂度：O(n + m)，递归调用的深度最多为两个链表的长度之和。

递归方法求解，代码简洁且易于理解，但仅适用于合并长度不是特别长的链表。对于非常长的链表，可能会因为递归深度过大而导致栈溢出。

循环迭代合并

_Gn!

递归是一个有风险的操作，虽然代码简洁思路容易理解，但当链表较长时具有栈溢出风险。所以我们还需要掌握另一种循环迭代的方式来有序合并两条有序链表。

循环迭代的方法有点像在两条链表间"穿针引线"将两条链表链接起来，它不会占用额外的内存空间，空间复杂度是O(1)

其实现实现是：

1. 先比较两条单链表的第一个结点，确定较小结点，这个较小结点就是合并后新链表的第一个结点。

2. 初始化head和tail指针，指向合并后新链表的第一个结点。

   1. 其中head指针用来作为返回值，所以整个合并过程不会移动该指针。

   2. tail指针用于标记指向合并后新链表的最后一个结点，所以tail指针就用于实现"穿针引线"。

3. 除了第一个结点外，其余结点可以使用一个循环来实现它们的"穿针引线"：

   1. 逐一比较链表对应位置的结点取值，将较小值的结点链接到tail结点后面

   2. 移动tail指针以及相应遍历链表的指针

4. "穿针引线"结束后，总会有一条链表为空，另一条链表非空。所以将非空链表链接到tail结点后面即可实现合并两条单链表。

不带头结点合并两条有序单链表，参考实现代码如下：

xxxxxxxxxx
51
1
// 合并两条有序单链表，并且返回新链表的头指针
2
Node *merge_lists(Node *list1, Node *list2) {
3
    // 1.处理链表为空的情况
4
    /*if (list1 == NULL){
5
        return list2;
6
    }
7
    if (list2 == NULL){
8
        return list1;
9
    }*/
10
    if (!list1 || !list2) { // 如果list1或者list2为NULL
11
        return list1 ? list1 : list2;
12
    }
13
    // 2.对两条单链表的第一个结点做判断处理,找到较小结点,用来初始化head和tail指针
14
    Node *head = NULL, *tail = NULL;
15
    if (list1->data < list2->data) {
16
        // list1的第一个结点是最小结点,它就是合并后单链表的第一个结点,也就是返回值头指针
17
        head = tail = list1;
18
        list1 = list1->next;
19
    }
20
    else {
21
        // list2的第一个结点是最小结点或者它们两第一个结点是一样的
22
        // 这时list2的第一个结点就是合并后单链表的第一个结点,也就是返回值头指针
23
        head = tail = list2;
24
        list2 = list2->next;
25
    }
26

27
    // 3.后续结点可以统一用循环处理,不需要单独处理了
28
    while (list1 != NULL && list2 != NULL) {    // 只要两条单链表都同时还有结点,那就继续"穿针引线"
29
        if (list1->data < list2->data) {
30
            // list1指向的结点是相对较小的结点,那就先"穿针引线"它
31
            tail->next = list1;
32
            tail = list1;
33
            list1 = list1->next;
34
        }
35
        else {
36
            // list2指向的结点是相对较小的结点或者两个结点取值一样,那就先"穿针引线"它
37
            tail->next = list2;
38
            tail = list2;
39
            list2 = list2->next;
40
        }
41
    }   // while循环结束时,两条单链表一定有一条是空的，而另一条非空
42
    // 但无所谓, 我们只需要判断一下,然后将非空链表链接到tail结点后面即可
43
    if (list1 != NULL) {
44
        tail->next = list1;
45
    }
46
    if (list2 != NULL) {
47
        tail->next = list2;
48
    }
49
    // 不要忘记给返回值
50
    return head;
51
}

不带头结点仍然是可以实现功能的，但缺点是需要对头部做额外的一次操作，这使得代码重复，操作不统一。于是我们就想要使用头结点，来统一头部的操作，简化代码。

其基本的思路是（两条链表分别是A和B）：

1. 创建一个虚拟头结点用于简化统一操作，再创建一个head指针先指向虚拟头结点，此时head指针就是一个头结点指针。再创建一个tail指针始终指向当前合并链表的最后一个结点，一开始tail指针指向虚拟头结点。

2. 循环遍历两个条件（条件是A和B链表都非空）：

   1. 比较链表A和链表B当前头节点的值，也就是比较函数传入的list1和list2指针指向的结点的值。

   2. 如果A的值更小，那么将A中的此结点添加到合并后的链表中，也就是让tail->next指向它，然后再更新tail指针，最后将A的头指针向后移动。

   3. 如果B的值更小或相等，那么将B中的此结点添加到合并后的链表中，也就是让tail->next指向它，然后再更新tail指针，最后将B的头指针向后移动。

   4. 注意：每一次循环都会像"穿针引线"一样，将两个链表中的某一个结点链接到结果链表的后面。

   5. 注意：虚拟头结点的存在，可以将链表的第一个结点的处理逻辑和后续结点的处理逻辑统一起来，从而简化操作代码，使得逻辑更通顺。这也是有头结点链表的方便之处，当然这不是必须的。直接用head指针指向合并后两个链表较小的第一个结点也可以实现功能，但这样链表第一个结点就需要做特殊化处理。

3. 遍历结束后，一定会有某一条链表为空，于是进行处理，将非空链表的所有结点全部链接起来：

   1. 如果list1非空，让tail->next指向list1

   2. 如果list2非空，让tail->next指向list2

4. 合并完成，将head->next返回，因为head指向的只是虚拟头结点，不是链表真正的第一个结点。

带头结点合并两条有序单链表，参考代码如下：

循环迭代合并链表（带头结点）-参考代码

xxxxxxxxxx
34
1
// 循环迭代合并有序链表
2
Node* merge_lists(Node* list1, Node* list2) {
3
    Node sup_head_node = {0, NULL};
4
    Node* head = &sup_head_node;
5
    Node* tail = head;
6

7
    // 循环遍历两个链表
8
    while (list1 != NULL && list2 != NULL){
9
        if (list1->data < list2->data){
10
            // list1的结点更小，将它链接到tail指针指向的结点后面
11
            tail->next = list1;
12
            // 更新向后挪动tail指针和list1指针
13
            tail = tail->next;
14
            list1 = list1->next;
15
        }
16
        else{
17
            // list2的结点更小或相等，将它链接到tail指针指向的结点后面
18
            tail->next = list2;
19
            // 更新向后挪动tail指针和list2指针
20
            tail = tail->next;
21
            list2 = list2->next;
22
        }
23
    }   // 循环结束时必有一条链表为空，现在将不为空的链表链接到tail结点后面
24

25
    /*if (list1 != NULL){
26
        tail->next = list1;
27
    }
28
    if (list2 != NULL) {
29
        tail->next = list2;
30
    }*/
31
    tail->next = list1 ? list1 : list2;
32
    // 最终要返回head->next，因为head指向的是头结点。下一个结点才是第一个有数据的结点
33
    return head->next;
34
}

分析：

时间复杂度：O(n + m)，其中n和m分别是两个链表的长度。这是由于每次循环处理1个结点的合并，那么循环就需要进行n + m次。

空间复杂度：O(1)，原地合并

可以看到，循环迭代求解最大的优势就是原地合并，并不需要额外的内存空间，这在处理长链表时非常有优势。

The End