_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节8链表阶段作业}

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

基础题篇

_Gn!

下面都是一些基础的语法、概念编程练习题。

手动实现一条单链表（基础题/重点）

_Gn!

基于以下头文件，手动实现一条单链表：

xxxxxxxxxx
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

手动实现单链表是后续一切数据结构学习的前提和基础，所以一定要重视单链表的实现，一定要自己百分百手动将这里面的函数全部实现。

参考代码如下：

参考代码：

以下是实现源文件的代码，即所有函数的实现如下：

xxxxxxxxxx
1
#include "linkedlist.h"
2
#include <stdio.h>
3
#include <stdlib.h>
4

5
// 创建一个空的链表
6
LinkedList *create_linked_list() {
7
    return calloc(1, sizeof(LinkedList));
8
}
9
// 销毁链表
10
void destroy_linked_list(LinkedList *list) {
11
    // 遍历整条链表,包括最后一个结点,然后逐一free
12
    Node *curr = list->head;
13
    while (curr != NULL) {
14
        Node *tmp = curr->next;
15
        free(curr);
16
        curr = tmp;
17
    }
18
    free(list);
19
}
20

21
// 头部插入结点
22
bool add_before_head(LinkedList *list, DataType data) {
23
    // 1.分配一个新结点,初始化它
24
    Node *new_node = malloc(sizeof(Node));
25
    if (new_node == NULL) {
26
        printf("error: malloc failed in add_before_head.\n");
27
        return false;
28
    }
29
    new_node->data = data;
30
    // 2.让新结点指向原本的第一个结点
31
    new_node->next = list->head;
32

33
    // 3.更新头指针
34
    list->head = new_node;
35

36
    // 考虑特殊情况
37
    //if(list->size == 0)
38
    if (list->tail == NULL) {
39
        // 说明头插之前链表为空, 更新尾指针
40
        list->tail = new_node;
41
    }
42
    list->size++;
43
    return true;
44
}
45
// 尾部插入结点
46
bool add_behind_tail(LinkedList *list, DataType data) {
47
    // 1.分配一个新结点,初始化它
48
    Node *new_node = malloc(sizeof(Node));
49
    if (new_node == NULL) {
50
        printf("error: malloc failed in add_behind_tail.\n");
51
        return false;
52
    }
53
    new_node->data = data;
54
    new_node->next = NULL;
55

56
    // 2.判断链表插入之前是否为空
57
    if (list->size == 0) {
58
        // 尾插之前链表为空
59
        list->head = new_node;
60
        list->tail = new_node;
61
        list->size++;
62
        return true;
63
    }
64
    // 链表尾插之前不为空
65
    list->tail->next = new_node;
66
    list->tail = new_node;
67
    list->size++;
68
    return true;
69
}
70
// 按索引插入结点
71
/*
72
    对于链表来说,第一个结点的索引规定是0,那么链表的结点索引合法范围是[0, size-1]
73
    分析:
74
    1.参数校验,对错误的参数进行错误的处理
75
    index在这个函数中,合法的取值范围是[0, size]
76
    其中0表示头插, size表示尾插
77

78
    2.处理特殊值,尾插和头插直接调用已实现的函数
79
    3.在index合法,且不是头插尾插,即在中间插入结点时
80
*/
81
bool add_by_idx(LinkedList *list, int index, DataType data) {
82
    if (index < 0 || index > list->size) {
83
        printf("Illegal Arguments: index = %d\n", index);
84
        return false;
85
    }
86
    if (index == 0) {
87
        return add_before_head(list, data);
88
    }
89
    if (index == list->size) {
90
        return add_behind_tail(list, data);
91
    }
92

93
    // 处理中间插入结点的情况
94
    Node *new_node = malloc(sizeof(Node));
95
    if (new_node == NULL) {
96
        printf("error: malloc failed in add_index.\n");
97
        return false;
98
    }
99
    new_node->data = data;
100

101
    // 遍历链表,找到index-1位置的结点
102
    Node *prev = list->head;
103
    for (int i = 0; i < index - 1; i++) {
104
        prev = prev->next;
105
    }   // for循环结束时,prev指针指向index索引的前驱结点
106

107
    // 让新结点指向prev的后继结点
108
    new_node->next = prev->next;
109
    // 让prev指向新结点
110
    prev->next = new_node;
111
    list->size++;
112
    return true;
113
}
114

115
// 根据索引搜索结点
116
Node *search_by_idx(LinkedList *list, int index) {
117
    if (index < 0 || index > list->size - 1) {  // size-1就是最后一个结点
118
        printf("Illegal Arguments: index = %d\n", index);
119
        return NULL;
120
    }
121
    // 索引合法
122
    Node *curr = list->head;
123
    for (size_t i = 0; i < index; i++)  // 小于index就表示寻找index索引的结点
124
    {
125
        curr = curr->next;
126
    }   // for循环结束时,curr指针指向index索引位置的结点
127
    return curr;
128
}
129

130
// 根据数据搜索结点
131
Node *search_by_data(LinkedList *list, DataType data) {
132
    // 惯用法遍历每一个结点,遍历过程中判断即可
133
    Node *curr = list->head;
134
    while (curr != NULL) {
135
        if (curr->data == data) {
136
            // 找到了
137
            return curr;
138
        }
139
        curr = curr->next;
140
    }
141
    // 遍历结束都没有return 说明没有找到
142
    return NULL;
143
}
144

145
// 根据数据删除结点
146
/*
147
    对于一条单链表来说, 在一个确定的结点的后面进行删除/新增操作, 它的时间复杂度是O(1)
148
    链表的结点删除,哪些是O(1)的呢?
149
    1.删除第一个结点是不是? 是,因为这个过程基本只需要改变头指针的指向就可以了
150
    2.删除最后一个结点是不是呢? 不是, 因为删除最后一个结点,需要找到倒数第二个结点,这需要遍历数组,时间复杂度是O(n)
151
    3.删除中间的结点是不是呢? 肯定不是,因为需要遍历找到这个结点
152
    于是将单链表的删除分解成两个步骤:
153
    1.假如删除的是第一个结点
154
    2.如果删除的是第一个结点外的其它结点
155

156
*/
157
bool delete_by_data(LinkedList *list, DataType data) {
158
    // 校验: 如果链表为空,不删除了
159
    if (list->head == NULL) {
160
        printf("链表为空,无法删除!\n");
161
        return false;
162
    }
163
    Node *curr = list->head;    // 该指针用于遍历整条单链表
164
    // 1.处理删除的是第一个结点的情况
165
    if (curr->data == data) {
166
        list->head = curr->next;    // 这步操作不论链表是否只有一个结点 都是要做的
167
        if (list->head == NULL) {
168
            // 说明链表仅有一个结点,删除后,要同步更新尾指针
169
            list->tail = NULL;
170
        }
171
        free(curr);
172
        list->size--;
173
        return true;
174
    }
175

176
    // 2.处理其他结点的删除情况
177
    // 已经有一个指针,叫curr,它目前指向第一个结点
178
    Node *prev = curr;
179
    curr = curr->next;
180

181
    while (curr != NULL) {  // 从第二个结点开始,遍历完整条单链表
182
        if (curr->data == data) {
183
            // 找到了待删除目标结点,curr指向它,此时prev指向它的前驱
184
            prev->next = curr->next;
185
            if (curr->next == NULL) {
186
                // 待删除结点是尾结点
187
                list->tail = prev;
188
            }
189
            free(curr);
190
            list->size--;
191
            return true;
192
        }
193
        prev = curr;
194
        curr = curr->next;
195
    } // while循环结束时,curr指针指向NULL,prev指向链表的最后一个结点
196

197
    // while循环结束都没有return, 说明没找到目标data的结点,删除失败
198
    return false;
199
}
200

201
// 根据索引删除结点
202
bool delete_by_idx(LinkedList *list, int idx) {
203
    if (list->head == NULL) {
204
        printf("链表为空,无法删除!\n");
205
        return false;
206
    }
207

208
    // 检查链表是否为空或索引是否越界
209
    if (idx < 0 || idx >= list->size) {
210
        printf("Illegal Arguments: index = %d\n", idx);
211
        return false;
212
    }
213

214
    Node *curr = list->head;
215
    Node *prev = NULL;
216

217
    // 如果要删除的是第一个结点
218
    if (idx == 0) {
219
        list->head = curr->next;  // 更新头指针
220
        // 若删除的结点是唯一的结点
221
        if (list->size == 1) {
222
            list->tail = NULL;  // 更新尾指针
223
        }
224
        free(curr);
225
        list->size--;
226
        return true;
227
    }
228

229
    // 如果删除的结点不是第一个结点
230
    for (int i = 0; i < idx; i++) {
231
        prev = curr;
232
        curr = curr->next;
233
    }
234

235
    // 让前驱结点指向后继结点
236
    prev->next = curr->next;
237

238
    // 如果要删除的是尾结点, 则需要更新尾指针
239
    if (idx == list->size - 1) {
240
        list->tail = prev;
241
    }
242

243
    free(curr);
244
    list->size--;
245
    return true;
246
}
247

248
// 打印单链表 格式为：1 -> 2 -> 3 ->...
249
void print_list(LinkedList *list) {
250
    Node *curr = list->head;
251
    // 遍历此单链表
252
    while (curr != NULL) {
253
        printf("%d", curr->data);
254
        // 如果不是链表的最后一个结点，就打印箭头
255
        if (curr->next != NULL) {
256
            printf(" -> ");
257
        }
258
        curr = curr->next;
259
    }
260
    printf("\n");
261
}

再给出一个测试用例，如下：

xxxxxxxxxx
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!

基于链表的结点定义：

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

以及相应的二级指针尾插法构建单链表：

xxxxxxxxxx
1
// 实现尾插法构建链表
2
void insert_tail(Node **head, int new_data) {
3
    // 1.分配新结点，初始化它
4
    Node *new_node = malloc(sizeof(Node));
5
    if (new_node == NULL) {
6
        printf("error: malloc failed in insert_tail.\n");
7
        exit(1);
8
    }
9
    new_node->data = new_data;
10
    new_node->next = NULL;
11
    // 3.链表非空时,让原本最后一个结点指向新结点
12
    if (*head != NULL) {
13
        // 2.遍历找到最后一个结点
14
        Node *end = *head;
15
        while (end->next != NULL) {
16
            end = end->next;
17
        } // while循环结束时, end指向最后一个结点
18
        end->next = new_node;
19
        return;
20
    }
21
    // 链表尾插之前是空的,那就直接更新头指针就行了
22
    *head = new_node;
23
}

后续单链表的面试题，也请基于此链表结点的定义，以及尾插法构建链表实现。

利用快慢指针法，直接求解下列两个问题：

1.求链表中间结点的值

2.判断单链表是否有环

注意：

不仅要定义函数实现对应功能，还需要编写测试用例，进行测试。尤其是测试单链表有环，要自己构建出一条有环的单链表进行测试。

参考代码如下：

参考代码：

求链表中间结点的值以及相应测试代码：

xxxxxxxxxx
1
int find_mid_ele(Node *head) {
2
    Node *fast = head, *slow = head;
3
    /*
4
        fast != NULL意味着偶数链表长度时,fast没有到终点
5
        fast->next != NULL意味着奇数链表长度时,fast没有到终点
6
    */
7
    while (fast != NULL && fast->next != NULL) {
8
        // fast指针没有到达终点
9
        slow = slow->next;
10
        fast = fast->next->next;
11
    }   // while循环结束时,fast到达终点了,slow指向中间结点
12
    return slow->data;
13
}
14
// 测试代码
15
int main(void) {
16
    Node *head = NULL;  // head代表链表的头指针，此时是一条空链表
17
    insert_tail(&head, 1);
18
    insert_tail(&head, 2);
19
    insert_tail(&head, 3);
20
    insert_tail(&head, 4);
21
    insert_tail(&head, 5);
22
    int ret = find_mid_ele(head);   // ret的值为3
23
    insert_tail(&head, 6);
24
    insert_tail(&head, 7);
25
    insert_tail(&head, 8);
26
    int ret2 = find_mid_ele(head);  // ret2的值为5
27
    return 0;
28
}

判断单链表有环以及相应测试代码：

xxxxxxxxxx
1
bool has_circle(Node *list) {
2
    Node *fast = list;
3
    Node *slow = list;
4

5
    while (fast != NULL && fast->next != NULL) {
6
        slow = slow->next;
7
        fast = fast->next->next;
8
        if (slow == fast) {
9
            return true;    // 相遇了就表示有环
10
        }
11
    }
12
    // 如果循环能够结束, 说明没有环
13
    return false;
14
}
15

16
// 测试代码
17
int main(void) {
18
    Node *head = NULL;  // head代表链表的头指针，此时是一条空链表
19
    insert_tail(&head, 1);
20
    insert_tail(&head, 2);
21
    insert_tail(&head, 3);
22
    insert_tail(&head, 4);
23
    insert_tail(&head, 5);
24

25
    /*
26
    构建出一条有环单链表
27
    1 -> 2 -> 3 -> 4 -> 5 -> 2 -> 3 -> 4 ....
28
    如何构建呢？
29
    1.找到单链表的尾结点（last指针来寻找它）
30
    2.在寻找尾结点的过程中, 记录一下结点2(用second指针记录)
31
    3.让last结点指向second结点
32
    */
33
    Node *last = head;
34
    Node *second = head;
35
    int count = 0;
36
    while (last->next != NULL) {
37
        count++;
38
        if (count == 2) {
39
            second = last;  // 记录一下结点2
40
        }
41
        last = last->next;
42
    }   // while循环结束时,second指针指向结点2, last指针指向结点5
43
    last->next = second;
44
    bool ret = has_circle(head);    // ret等于true，表示单链表有环
45
    return 0;
46
}

以上。

链表基础面试题：反转单链表

_Gn!

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

举例：

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

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

基于以下函数的声明实现：

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

注意：

请采用递归和循环迭代两种方式求解这个问题。

参考代码如下：

参考代码如下：

两种方式实现反转单链表，参考代码如下：

x
1
/*
2
    循环迭代的方式实现单链表的反转操作：三指针法
3
    在循环的过程中：
4
    让curr结点指向prev结点
5
    然后向后移动三个指针
6
*/
7
Node *reverse_list_loop(Node *head) {
8
    Node *prev = NULL;
9
    Node *curr = head;
10
    /*
11
        next如果定义在循环的外面，那么在while循环当中就需要手动来更新next指针
12
            next = curr -> next
13
            而且这个更新还需要判断，curr不是空指针
14
        next如果定义在循环的内部，那么在while循环当中就不需要手动来更新next指针了
15
            因为每循环一次就重新给next指针赋值，而这个赋值就是next = curr->next
16
            而且也不用给curr判NULL了，因为curr是NULL时，循环停止了，进不到循环体
17
    */
18
    //Node *next = curr->next;
19
    while (curr != NULL) {
20
        Node *next = curr->next;
21
        curr->next = prev;  // 反转的核心操作
22
        prev = curr;
23
        curr = next;
24
        /*if (curr != NULL) {
25
            next = curr->next;
26
        }*/
27
    }
28
    return prev;
29
}
30

31
// 递归的方式反转单链表
32
Node *reverse_list_recursion(Node *head) {
33
    // 1.递归的出口
34
    if (head == NULL || head->next == NULL) {
35
        return head;
36
    }
37
    // 2.递归体
38
    // 1.先完成n-1个结点的反转
39
    Node *ret = reverse_list_recursion(head->next);
40
    // 2.让原本的第二个结点指向原本的第一个结点
41
    head->next->next = head;
42
    // 3.反转第一个结点
43
    head->next = NULL;
44
    return ret;
45
}

测试用例如下：

x
1
int main(void) {
2

3
    Node *head = NULL;  // head代表链表的头指针，此时是一条空链表
4
    insert_tail(&head, 1);
5
    insert_tail(&head, 2);
6
    insert_tail(&head, 3);
7
    insert_tail(&head, 4);
8
    insert_tail(&head, 5);
9

10
    // 单链表的反转，最终得到单链表 5 -> 4 -> 3 -> 2 -> 1 
11
    // head = reverse_list_loop(head);
12
    // head = reverse_list_recursion(head);
13

14
    return 0;
15
}

以上。

链表基础面试题：合并两条有序单链表

_Gn!

合并两条有序的单向链表，使得合并后的链表也是有序的 (要求: 不能额外申请堆内存空间)。

输入：

list1: 1 --> 3 --> 5

list2: 2 --> 4 --> 6

输出：

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

可以直接基于以下函数声明来进行实现。

xxxxxxxxxx
1
1
Node* merge_two_lists(Node* list1, Node* list2);    // 合并两条有序单链表，并返回合并后新链表的头指针

要求使用递归和循环迭代两种方式实现这个功能。

注：循环实现时，可以思考一下加头结点的实现与不加的区别。

不仅要定义函数实现对应功能，还需要编写测试用例，进行测试。

参考代码如下：

参考代码：

循环迭代方式实现合并有序单链表，不带头结点的实现：

x
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
}

循环迭代方式实现合并有序单链表，带头结点的实现：

x
1
// 带有头结点,以合并两条有序单链表
2
Node *merge_lists2(Node *list1, Node *list2) {
3
    // 1.处理链表为空的情况
4
    if (!list1 || !list2) { // 如果list1或者list2为NULL
5
        return list1 ? list1 : list2;
6
    }
7

8
    // 2.创建虚拟头结点,初始化head和tail指针
9
    Node head_node = { 0, NULL };
10
    Node *head = &head_node, *tail = &head_node;
11

12
    // 3.循环遍历两条单链表,逐一比较对应位置的结点值,将较小的结点链接到tail结点的后面
13
    while (list1 != NULL && list2 != NULL) {    // 只要两条单链表都同时还有结点,那就继续"穿针引线"
14
        if (list1->data < list2->data) {
15
            // list1结点较小,它被合并到新链表中
16
            tail->next = list1;
17
            tail = list1;
18
            list1 = list1->next;
19
        }
20
        else {
21
            // list2结点较小或者两个位置的结点取值一样,它被合并到新链表中
22
            tail->next = list2;
23
            tail = list2;
24
            list2 = list2->next;
25
        }
26
    }   // while循环结束时,必然有一条链表为空,另一条不为空
27

28
    // 4.循环合并结束后,总会有一条链表为空,另一条非空,判断一下将非空链表链接到tail结点后面
29
    if (list1 != NULL) {
30
        tail->next = list1;
31
    }
32
    if (list2 != NULL) {
33
        tail->next = list2;
34
    }
35

36
    // 5.不要忘记给出函数的返回值
37
    return head->next;  // 函数出栈后,head_node这个局部变量结点就被销毁了
38
}

递归方式实现合并有序单链表，参考实现代码如下：

x
1
// 递归的方式合并两条单链表
2
Node *merge_lists_recursion(Node *list1, Node *list2) {
3
    // 1.递归的出口
4
    if (!list1 || !list2) { // 如果list1或者list2为NULL
5
        return list1 ? list1 : list2;
6
    }
7

8
    // 2.递归体
9
    // 比较两条链表的第一个结点取值,然后取较小的结点作为合并单链表的第一个结点,而且它还是函数的返回值
10
    if (list1->data < list2->data) {
11
        // list1指向的结点是较小的,list1就是合并后新链表的第一个结点
12
        list1->next = merge_lists_recursion(list1->next, list2);
13
        return list1;
14
    }
15
    else {
16
        // list2指向的结点是较小或者两个结点相等,list2就是合并后新链表的第一个结点
17
        list2->next = merge_lists_recursion(list1, list2->next);
18
        return list2;
19
    }
20
}

测试代码如下：

x
1
int main(void) {
2
    Node *list1 = NULL;
3
    Node *list2 = NULL;
4
    insert_tail(&list1, 1);
5
    insert_tail(&list1, 3);
6
    insert_tail(&list1, 5);
7
    insert_tail(&list1, 7);
8

9
    insert_tail(&list2, 2);
10
    insert_tail(&list2, 4);
11
    insert_tail(&list2, 6);
12
    insert_tail(&list2, 8);
13
    insert_tail(&list2, 9);
14

15
    // 合并成功后的单链表是 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
16
    // Node *ret = merge_lists(list1, list2);   
17
    // Node *ret2 = merge_lists2(list1, list2);
18
    // Node *ret3 = merge_lists_recursion(list1, list2);
19
}

以上。

扩展题篇

_Gn!

以下题目都属于扩展题。

以下单链表的扩展编程题，都基于以下链表结点的定义，以及一个尾插法构建单链表的实现：

x
1
typedef struct Node {
2
    int data;
3
    struct Node *next;
4
} Node;
5

6
// 尾插法
7
void insert_tail(Node **head, int val) {
8
    Node *new_node = calloc(1, sizeof(Node));   // 用calloc避免忘记设置next域为NULL
9
    if (new_node == NULL) {
10
        printf("malloc failed in insert_tail.\n");
11
        exit(1);
12
    }
13
    new_node->data = val;
14
    if (*head == NULL) {
15
        *head = new_node;
16
    }
17
    else {
18
        Node *curr = *head;
19
        while (curr->next != NULL) {
20
            curr = curr->next;
21
        }
22
        curr->next = new_node;
23
    }
24
}

接下来请你实现以下一些功能。

扩展：删除连续重复结点

_Gn!

删除单链表中连续出现的重复节点，具体来说，当链表中有相邻的两个或多个节点的值相同时，删除后续的重复节点，只保留第一个出现的节点。

举例：

单链表：1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5

删除后将得到链表：1 -> 2 -> 3 -> 4 -> 5

 

单链表：1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4

删除后将得到链表：1 -> 2 -> 3 -> 4

请基于以下函数声明实现这个功能：

xxxxxxxxxx
1
1
void del_continuous_repeat(Node *head);

注：该函数不会修改头指针，所以使用一级指针传参且函数也没有返回值。

参考代码如下：

参考代码实现如下：

x
1
// 删除连续的重复节点，注意链表结点定义以及尾插函数已经被省略了
2
void del_continuous_repeat(Node *head) {
3
    // 如果链表为空或仅有一个结点,则无事发生
4
    if (head == NULL || head->next == NULL) {
5
        return;
6
    }
7
    Node *curr = head;
8
    while (curr->next != NULL) {
9
        if (curr->data == curr->next->data) {
10
            /*
11
                如果当前结点curr和后继结点curr->data的data相同, 则出现连续重复结点
12
                此时需要删除一个结点,并free
13
                那么删除哪一个结点呢?
14
                删除curr结点还是curr->next结点呢?
15
                当然是删除curr->next结点
16
                因为单链表的删除只能在确定结点的后面执行删除操作, 才是O(1)时间复杂度
17
            */
18
            Node *tmp = curr->next; // 记录curr->next结点,后续用于free
19
            /*
20
                删除curr->next结点
21
                需要curr->next结点的前驱结点指向curr->next的后继结点,也就是从链表中将curr->next结点绕过去
22
                curr->next结点前驱是curr结点
23
                curr->next结点后继是curr->next->next结点,也就是tmp->next
24
            */
25
            curr->next = tmp->next;     // 删除核心逻辑代码
26
            free(tmp);
27
        }
28
        else {
29
            // 没有重复结点,继续遍历结点
30
            curr = curr->next;
31
        }
32
    }
33
}
34

35
// 以下是测试代码，链表结点定义以及尾插代码省略了
36
int main(void) {
37
    Node *head = NULL;
38
    insert_tail(&head, 1);
39
    insert_tail(&head, 2);
40
    insert_tail(&head, 2);
41
    insert_tail(&head, 3);
42
    insert_tail(&head, 4);
43
    insert_tail(&head, 4);
44
    insert_tail(&head, 4);
45
    insert_tail(&head, 5);
46
    // 此时单链表是：1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5
47

48
    del_continuous_repeat(head);    // 删除操作后，单链表是 1 -> 2 -> 3 -> 4 -> 5
49
    return 0;
50
}

以上。

扩展：检查回文单链表

_Gn!

给定一条单链表，请检查它是否为回文单链表。所谓回文单链表，即从头到尾和从尾到头数据都相同的单链表。

举例：

1 -> 2 -> 3 -> 2 -> 1 就是一条回文单链表

1 -> 2 -> 2 -> 1 也是一条回文单链表

请基于以下函数声明实现这个功能：

xxxxxxxxxx
1
1
bool is_palindrome_list(Node *head);

注意：

1. 针对单链表进行回文检查，不应改变此链表的结构。若程序必须改变链表结构，需在判断完成后还原。

2. 空链表或只有一个结点的链表默认就是回文链表。

提示，检查回文链表只需要以下几步就可以实现了：

1. 找到单链表的中间结点

2. 将链表的后半部分反转（思考反转的起点是哪一个结点？）

3. 将反转后半部分的结点和前半部分逐一比较，如果数据都相同则是回文链表，若有任一结点不同则不是回文链表。

4. 此过程会改变链表结构，所以需要考虑还原。（如何实现这个还原操作呢？）

参考代码如下：

参考代码实现如下：

x
1
// 反转单链表
2
Node *reverse(Node *head) {
3
    Node *prev = NULL;
4
    Node *current = head;
5

6
    while (current != NULL) {
7
        Node *next = current->next;
8
        current->next = prev;
9
        prev = current;
10
        current = next;
11
    }
12
    return prev;
13
}
14

15
// 快慢指针法找到链表中间节点，并确定链表长度的奇偶性
16
Node *find_mid_node(Node *head, bool *is_odd) {
17
    if (head == NULL) {
18
        return NULL;
19
    }
20
    Node *slow = head, *fast = head;
21
    while (fast != NULL && fast->next != NULL) {
22
        slow = slow->next;
23
        fast = fast->next->next;
24
    }
25
    *is_odd = (fast != NULL);  // 如果fast不为空，则链表长度为奇数
26
    return slow;
27
}
28

29
// 检查链表是否为回文
30
bool is_palindrome_list(Node *head) {
31
    if (head == NULL || head->next == NULL) {
32
        // 空链表或单个节点的链表默认是回文的
33
        return true;
34
    }
35

36
    bool is_odd;    // 链表长度的奇偶性
37
    // 找到中间节点以及确定链表长度的奇偶性
38
    Node *mid_node = find_mid_node(head, &is_odd);
39

40
    /*
41
        反转单链表的后半部分
42
        这里存在一个问题：怎么界定链表的前半部分和后半部分呢？
43
        奇数长度的单链表：以中间结点为界限分为前后两个部分
44
        偶数长度的单链表：以中间的两个结点为界限分为前后两个部分
45
        所以反转单链表的后半部分时：
46
        1.若链表长度是奇数，则从中间结点的下一个结点开始反转，并且在比较时也不比较中间结点。
47
        2.若链表长度是偶数，则从中间结点开始反转，并且在比较时也要比较这个中间结点。
48
    */
49
    Node *second_half;  // 反转后，后半部分链表的头指针
50
    if (is_odd) {
51
        second_half = reverse(mid_node->next);
52
    }
53
    else {
54
        second_half = reverse(mid_node);
55
    }
56
    // 记录后半部分链表的头指针，用于后续恢复链表
57
    Node *tmp_second = second_half;
58

59
    // 比较前后两部分的节点数据
60
    Node *first_half = head;
61
    bool is_palindrome = true;    // 链表是否是回文链表
62
    while (second_half != NULL) {   // 遍历后半部分链表
63
        if (first_half->data != second_half->data) {
64
            // 前后部分链表结点取值有任一不同，不是回文单链表
65
            is_palindrome = false;
66
        }
67
        first_half = first_half->next;
68
        second_half = second_half->next;
69
    }
70
    // 恢复原始链表
71
    reverse(tmp_second);    // 反转后半部分即可
72

73
    return is_palindrome;    // 是回文单链表
74
}
75

76
// 以下是测试代码，链表结点定义以及尾插代码省略了
77
int main(void) {
78
    // 测试用例 1：偶数长度回文链表
79
    Node *head1 = NULL;
80
    insert_tail(&head1, 1);
81
    insert_tail(&head1, 2);
82
    insert_tail(&head1, 3);
83
    insert_tail(&head1, 3);
84
    insert_tail(&head1, 2);
85
    insert_tail(&head1, 1);
86
    bool ret1 = is_palindrome_list(head1);
87

88
    // 测试用例 2：奇数长度回文链表
89
    Node *head2 = NULL;
90
    insert_tail(&head2, 1);
91
    insert_tail(&head2, 2);
92
    insert_tail(&head2, 3);
93
    insert_tail(&head2, 4);
94
    insert_tail(&head2, 3);
95
    insert_tail(&head2, 2);
96
    insert_tail(&head2, 1);
97
    bool ret2 = is_palindrome_list(head2);
98

99
    // 测试用例 3：偶数长度非回文链表
100
    Node *head3 = NULL;
101
    insert_tail(&head3, 1);
102
    insert_tail(&head3, 2);
103
    insert_tail(&head3, 3);
104
    insert_tail(&head3, 4);
105
    insert_tail(&head3, 2);
106
    insert_tail(&head3, 1);
107
    bool ret3 = is_palindrome_list(head3);
108

109

110
    // 测试用例 4：奇数长度非回文链表
111
    Node *head4 = NULL;
112
    insert_tail(&head4, 1);
113
    insert_tail(&head4, 2);
114
    insert_tail(&head4, 3);
115
    insert_tail(&head4, 4);
116
    insert_tail(&head4, 5);
117
    bool ret4 = is_palindrome_list(head4);
118

119
    return 0;
120
}

以上。

扩展：实现真正意义上的链表结点去重

_Gn!

给定一个单链表，请编写一个函数来删除链表中所有重复的节点，只保留第一次出现的节点，注意这里不再强调重复结点连续出现，允许间断出现。

举例：

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

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

注意：要求在O(n)的时间复杂度内，完成这个问题的求解。

提示：计数去重，这是非常典型的哈希表的应用场景，不妨考虑使用哈希表来完成这个操作。

参考代码

首先给出单链表和哈希表实现的头文件：

x
1
#ifndef HASH_TABLE_H
2
#define HASH_TABLE_H
3

4
#include <stdbool.h>
5
#include <stdint.h>
6
// 为了能够针对单链表结点去重，所以包含单链表头文件，以包含单链表的相关定义
7
#include "linked_list.h"
8

9
#define DEFAULT_CAPACITY 8  // 哈希表的初始默认容量是8
10

11
// 哈希表的结点类型
12
typedef struct hash_node {
13
    ElementType key;    // 哈希表只存储key，key是单链表中的元素，实现去重时，它是唯一的
14
    struct hash_node *next;
15
} HashNode;
16

17
// 由于链表的长度不确定，所以我们使用一个动态哈希表
18
typedef struct {
19
    HashNode **buckets; 
20
    int size;               // 键值对的个数
21
    int capacity;           // 哈希表底层数组的长度
22
    uint32_t hash_seed;     // 哈希函数需要的种子值
23
} DynamicHashMap;
24

25
// 创建一个空的初始容量是8的哈希表
26
DynamicHashMap *create_hashmap();
27

28
// 销毁哈希表
29
void destroy_hashmap(DynamicHashMap *map);
30

31
// 向哈希表添加元素
32
bool put(DynamicHashMap *map, ElementType key);
33

34
// 检查哈希表是否包含某个元素
35
bool is_contains(DynamicHashMap *map, ElementType key);
36

37
#endif // HASH_TABLE_H
38

39

40
// ------------------------------------------------- //
41

42
#include <stdio.h>
43
typedef int ElementType;
44

45
typedef struct list_node {
46
    ElementType data;
47
    struct list_node *next;
48
} Node;
49

50
// 二级指针尾插法构建单链表
51
void insert_tail(Node **head, ElementType val);

紧接着是哈希表的实现源文件：

x
1
#include "hash_map.h"
2

3
#define LOAD_FACTOR_THRESHOLD  0.75     // 负载因子的阈值
4
#define CAPACITY_THRESHOLE 1024     // 数组容量的阈值
5

6
/* murmur_hash2 */
7
static uint32_t hash(const void *key, int len, uint32_t seed) {
8
    const uint32_t m = 0x5bd1e995;
9
    const int r = 24;
10
    uint32_t h = seed ^ len;
11
    const unsigned char *data = (const unsigned char *)key;
12

13
    while (len >= 4) {
14
        uint32_t k = *(uint32_t *)data;
15
        k *= m;
16
        k ^= k >> r;
17
        k *= m;
18
        h *= m;
19
        h ^= k;
20
        data += 4;
21
        len -= 4;
22
    }
23

24
    switch (len) {
25
        case 3: h ^= data[2] << 16;
26
        case 2: h ^= data[1] << 8;
27
        case 1: h ^= data[0];
28
            h *= m;
29
    };
30

31
    h ^= h >> 13;
32
    h *= m;
33
    h ^= h >> 15;
34

35
    return h;
36
}
37

38
static void rehash(HashNode *curr, HashNode **new_table, int new_capacity, uint32_t seed) {
39
    // 计算 key 的哈希值
40
    int idx = hash(&(curr->key), sizeof(ElementType), seed) % new_capacity;
41
    // 头插法
42
    curr->next = new_table[idx];
43
    new_table[idx] = curr;
44
}
45

46
// 对哈希表进行扩容操作
47
static void grow_capacity(DynamicHashMap *map) {
48
    /*
49
    * 扩容策略：
50
    * 1.如果容量没有达到阈值，那就每次将长度扩大为原先的2倍
51
    * 2.如果容量达到阈值，此时哈希表已经很长了，为了避免扩容过程性能损耗过大
52
    *   所以扩容保守一些，每次只扩容阈值长度的容量
53
    *
54
    * 扩容的过程：
55
    * 1.每个键值对结点都要重新计算哈希值，重新映射到新哈希桶中(新数组)
56
    * 2.原先的动态数组的链表很复杂，难以进行重哈希操作，建议直接丢弃它
57
    * 重新创建一个新动态数组
58
    */
59
    int new_capacity =
60
        (map->capacity <= CAPACITY_THRESHOLE) ?
61
        (map->capacity << 1) :
62
    (map->capacity + CAPACITY_THRESHOLE);
63

64
    // 动态数组扩容需要使用 calloc
65
    HashNode **new_buckets = calloc(new_capacity, sizeof(HashNode *));
66
    if (new_buckets == NULL) {
67
        printf("Error: calloc failed in grow_capacity\n");
68
        exit(1);
69
    }
70
    // 每次扩容都更改一次哈希种子，提高安全性
71
    uint32_t seed = time(NULL);
72

73
    // 将所有键值对重新映射到新数组中
74
    for (int i = 0; i < map->capacity; i++) {
75
        HashNode *curr = map->buckets[i];
76
        while (curr != NULL) {
77
            HashNode *next = curr->next;
78
            // 重新进行哈希映射
79
            rehash(curr, new_buckets, new_capacity, seed);
80
            curr = next;
81
        }
82
    }
83
    // 将旧动态数组free，但是注意不要free键值对结点，结点已经被链接到新数组中了。
84
    free(map->buckets);
85
    // 更新 HashMap 的信息
86
    map->buckets = new_buckets;
87
    map->capacity = new_capacity;
88
    map->hash_seed = seed;
89
}
90

91
// 创建一个空的初始容量是8的哈希表
92
DynamicHashMap *create_hashmap() {
93
    DynamicHashMap *map = malloc(sizeof(DynamicHashMap));
94
    if (map == NULL) {
95
        printf("Error: malloc failed in hashmap_create\n");
96
        exit(1);
97
    }
98
    map->buckets = calloc(DEFAULT_CAPACITY, sizeof(HashNode *));
99
    if (map->buckets == NULL) {
100
        // 不要忘记先free结构体
101
        free(map);
102
        printf("Error: calloc failed in hashmap_create\n");
103
        exit(1);
104
    }
105
    // 初始化其它成员
106
    map->size = 0;
107
    map->capacity = DEFAULT_CAPACITY;
108
    map->hash_seed = time(NULL);
109
    return map;
110
}
111

112
// 销毁哈希表
113
void destroy_hashmap(DynamicHashMap *map) {
114
    // 1.先遍历动态数组销毁链表的每一个结点
115
    for (int i = 0; i < map->capacity; i++) {
116
        HashNode *curr = map->buckets[i];
117
        while (curr != NULL) {
118
            HashNode *tmp = curr->next;
119
            free(curr);
120
            curr = tmp;
121
        }
122
    }
123
    // 2.再销毁动态数组
124
    free(map->buckets);
125
    // 3.最后销毁哈希表结构体
126
    free(map);
127
}
128

129
// 向哈希表添加元素
130
bool put(DynamicHashMap *map, ElementType key) {
131
    // 计算key的哈希值确定存储位置
132
    int idx = hash(&key, sizeof(ElementType), map->hash_seed) % (map->capacity);
133

134
    // 遍历链表
135
    HashNode *curr = map->buckets[idx];
136
    while (curr != NULL) {
137
        if (key == curr->key) {
138
            // 此结点取值已经存在，不存入直接返回false
139
            return false;
140
        }
141
        curr = curr->next;
142
    } // while循环结束时, curr是一个NULL
143

144
    // 键值对不存在，即需要将键值对插入
145
    // 插入操作前需要计算当前哈希表的负载因子
146
    double load_factor = (1.0 * map->size) / (map->capacity);
147
    if (load_factor >= LOAD_FACTOR_THRESHOLD) {
148
        // 当前哈希表负载因子已达到阈值，将动态数组进行扩容
149
        grow_capacity(map);
150
        // 数组长度已变，需要再哈希确定当前键值对的存储位置
151
        idx = hash(&key, sizeof(ElementType), map->hash_seed) % (map->capacity);
152
    }
153
    // 开始插入新键值对
154
    HashNode *new_node = malloc(sizeof(HashNode));
155
    if (new_node == NULL) {
156
        printf("Error: malloc failed in hashmap_put\n");
157
        exit(1);
158
    }
159
    // 初始化结点
160
    new_node->key = key;
161
    // 链表的头插法
162
    new_node->next = map->buckets[idx];
163
    map->buckets[idx] = new_node;
164

165
    // 不要忘记更新size
166
    map->size++;
167
    return true;
168
}
169

170
// 检查哈希表是否包含某个元素
171
bool is_contains(DynamicHashMap *map, ElementType key) {
172
    // 计算key的哈希值确定存储位置
173
    int idx = hash(&key, sizeof(ElementType), map->hash_seed) % (map->capacity);
174

175
    // 遍历链表
176
    HashNode *curr = map->buckets[idx];
177
    while (curr != NULL) {
178
        if (key == curr->key) {
179
            // 此结点取值已经存在，返回true
180
            return true;
181
        }
182
        curr = curr->next;
183
    } // while循环结束时, 说明没找到目标结点值
184
    return false;
185
}

紧接着是链表的实现源文件：

x
1
#include "linked_list.h"
2

3
// 二级指针单链表尾插法
4
void insert_tail(Node **head, int val) {
5
    Node *new_node = calloc(1, sizeof(Node));   // 用calloc避免忘记设置next域为NULL
6
    if (new_node == NULL) {
7
        printf("malloc failed in insert_tail.\n");
8
        exit(1);
9
    }
10
    new_node->data = val;
11
    if (*head == NULL) {
12
        *head = new_node;
13
    }
14
    else {
15
        Node *curr = *head;
16
        while (curr->next != NULL) {
17
            curr = curr->next;
18
        }
19
        curr->next = new_node;
20
    }
21
}

最后是实现单链表去重，以及相关的测试代码：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <string.h>
5
#include "hash_map.h"
6

7
// 删除链表中的重复节点
8
void remove_duplicates(Node *head) {
9
    if (head == NULL) {
10
        return;
11
    }
12
    // 创建哈希表
13
    DynamicHashMap *map = create_hashmap();
14
    // 接下来需要执行单链表删除操作,所以需要prev和curr两个指针
15
    Node *curr = head;
16
    Node *prev = NULL;
17
    while (curr != NULL) {
18
        if (is_contains(map, curr->data)) {
19
            // 当前节点的值已存在，删除当前节点
20
            prev->next = curr->next; // 单链表删除结点的核心操作
21
            free(curr);
22
            curr = prev->next;  // 删除结点后,让curr指向prev的后继结点,此时prev和curr仍然保持跟随关系
23
        }
24
        else {
25
            // 当前节点的值不存在，将此结点值存入哈希表
26
            put(map, curr->data);
27
            prev = curr;
28
            curr = curr->next;
29
        }
30
    }
31
    // 销毁哈希表
32
    destroy_hashmap(map);
33
}
34

35
// 打印链表
36
void print_list(Node *head) {
37
    Node *current = head;
38
    while (current != NULL) {
39
        printf("%d", current->data);
40
        if (current->next != NULL) {
41
            printf(" -> ");
42
        }
43
        current = current->next;
44
    }
45
    printf("\n");
46
}
47

48
int main(void) {
49
    // 构建出一条有重复结点的单链表
50
    Node *head = NULL;
51
    insert_tail(&head, 1);
52
    insert_tail(&head, 2);
53
    insert_tail(&head, 3);
54
    insert_tail(&head, 2);
55
    insert_tail(&head, 4);
56
    insert_tail(&head, 3);
57
    insert_tail(&head, 5);
58

59
    printf("原始单链表1是: ");
60
    print_list(head);
61
    remove_duplicates(head);    // 去重的最终结果是: 1 -> 2 -> 3 -> 4 -> 5
62
    printf("去重后单链表1是: ");
63
    print_list(head);
64
    printf("\n");
65

66
    Node *head2 = NULL;
67
    // 构建一个200个结点的链表,但其中有100个结点是重复的
68
    for (int i = 0; i < 100; i++) {
69
        insert_tail(&head2, i % 10);  // 插入一些重复元素
70
        insert_tail(&head2, i);       // 插入一些唯一元素
71
    }
72
    printf("原始单链表2是: ");
73
    print_list(head2);
74

75
    remove_duplicates(head2);   // 去重的最终结果是: 1 -> 2 -> ... -> 99
76
    printf("去重后单链表2是: ");
77
    print_list(head2);
78
    return 0;
79
}

以上。