链表（C语言版）

文章目录 链表1.1 单链表基本操作实现代码运行结果 1.2 双向链表1.3 常见面试题

链表

链表：是用"链"将结点串联起来的数据结构。

结点：是一个对象(在C语言中就是一个结构体)。该对象中有数据域和指针域，数据域顾名思义存放的就是数据，指针域存放的是结点(可以是另一个结点，也可以是自身)的地址。

链表的分类：

循环链表我们用的一般比较少，但是当处理的数据具有环形结构时，就特别适合用循环链表，比如约瑟夫环问题。接下来我们讨论下最常用单向链表和双向链表。

1.1 单链表 基本操作

添加 (在某个结点后面添加) O(1)

删除 (在某个结点后面删除) O(1)

查找

a. 根据索引查找结点 O(n)

b. 查找链表中与特定值相等的结点（大小有序O(n) 大小无序O(n)）

实现 代码 // main.c #include <stdio.h> #include "list.h" int main(void) { List* list = create_list(); add_node(list, 0, 'A'); add_before_head(list, '1'); add_before_head(list, '2'); add_before_head(list, '3'); add_before_head(list, '4'); add_behind_tail(list, '5'); add_behind_tail(list, '6'); add_behind_tail(list, '7'); add_behind_tail(list, '8'); add_node(list, 4, 'Z'); traverse_list(list); delete_node(list, '4'); traverse_list(list); delete_node(list, '8'); traverse_list(list); delete_node(list, '9'); traverse_list(list); Node* findNode = find_by_index(list, 5); if (findNode != NULL) printf("链表索引为5的结点值为：%c\n", findNode->val); search_for_value(list, '7'); search_for_value(list, '9'); destroy_list(list); return 0; } // List.h // 定义结点类型 typedef struct node { char val; struct node* next; } Node; // 存放整条链表的信息 typedef struct { Node* head; Node* tail; int size; } List; // API List* create_list(); void destroy_list(List* list); void add_before_head(List* list, char val); void add_behind_tail(List* list, char val); void add_node(List* list, int idx, char val); void delete_node(List* list, char val); void traverse_list(List* list); Node* find_by_index(List* list, int idx); Node* search_for_value(List* list, char val); // List.c #include <stdio.h> #include "list.h" #include <malloc.h> // 创建链表 List* create_list() { List* list = (List*)malloc(sizeof(List)); list->head = NULL; list->tail = NULL; list->size = 0; // 创建list结构体之后，list->head和list->tail都是NULL， // 直接访问list->head->next和list->tail->next会导致解引用未初始化的指针，引发未定义行为（通常是程序崩溃）。 // list->head->next = NULL; /* WRONG */ // list->tail->next = NULL; /* WRONG */ return list; } // 释放链表 void destroy_list(List* list) { // 1. 释放所有结点 Node* cur = list->head; while (cur != NULL) { Node* next = cur->next; free(cur); cur = next; } // 2. 释放List结构体 free(list); printf("链表释放成功\n"); } // 头插法 void add_before_head(List* list, char val) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->val = val; newNode->next = list->head; list->head = newNode; if (list->tail == NULL) // 最初插入的结点作为尾节点 list->tail = newNode; list->size++; } // 尾插法 void add_behind_tail(List* list, char val) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->val = val; newNode->next = NULL; if (list->head == NULL) // 最先插入的结点为头结点 list->head = newNode; if (list->tail != NULL) list->tail->next = newNode; list->tail = newNode; list->size++; } // 索引插入 void add_node(List* list, int idx, char val) { if (idx < 0 || idx > list->size) { printf("链表索引输入错误\n"); return; } if (idx == 0) { // 头插 add_before_head(list, val); return; } if (idx == list->size) { // 尾插 add_behind_tail(list, val); return; } // 在链表中间插入的情况 Node* cur = list->head; for (int i = 0; i < idx - 1; i++) { cur = cur->next; } // i = idx - 1 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->val = val; newNode->next = NULL; newNode->next = cur->next; cur->next = newNode; list->size++; } // 删除链表结点 void delete_node(List* list, char val) { if (list->head == NULL) { printf("空链表，无法删除结点\n"); return; } Node* prev = NULL; Node* cur = list->head; while (cur != NULL) { if (cur->val == val) { // 找到了要删除的元素 // 注意头结点和尾结点是否改变 if (cur == list->head) // 如果要删除的是头结点 list->head = cur->next; if (cur == list->tail) // 如果要删除的是尾结点 list->tail = prev; Node* pTmp = cur; if (prev != NULL) prev->next = cur->next; free(pTmp); pTmp = NULL; list->size--; printf("成功删除元素：%c\n\n", val); return; } prev = cur; cur = cur->next; } // 链表里没有要删除的结点 printf("链表中找不到要删除的结点 %c\n\n", val); } // 遍历链表 void traverse_list(List* list) { Node* cur = list->head; printf("元素个数：%d\n", list->size); printf("头结点元素：%c 尾结点元素：%c\n", list->head->val, list->tail->val); while (cur != NULL) { printf("%c ", cur->val); cur = cur->next; } printf("\n\n"); } // 按索引查找 Node* find_by_index(List* list, int idx) { if (idx < 0 || idx > (list->size - 1)) { printf("链表索引输入错误\n"); return NULL; } Node* cur = list->head; for (int i = 0; i < idx; i++) { cur = cur->next; } return cur; } // 按值查找 Node* search_for_value(List* list, char val) { Node* cur = list->head; while (cur != NULL) { if (cur->val == val) { printf("找到了目标结点 %c\n", val); return cur; } cur = cur->next; } printf("链表中找不到目标结点 %c\n", val); return NULL; } 运行结果

1.2 双向链表

我们很容易验证，单向链表的基本操作，双向链表也是支持的，并且时间复杂度也是一样。但是在工程实践上，我们往往更倾向于使用双向链表，而不是单链表，比如 C++ 中的 list，Java 中的 LinkedList 底层的数据结构都是双向链表。

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

添加 可以在某个结点前面添加

删除（可以当前结点）

查找

a. 根据索引查找结点 O(n), 平均只需遍历 n/4 各结点。

b. 查找链表中与特定值相等的结点（大小有序，（查找多个值时）保留上次查找结点的地址； 大小无序O(n)，与单链表一致）

总结：虽然双向链表更占内存空间，但是它某些操作的性能是优于单链表的。这就是典型的空间换时间的思想。

空间换时间：缓存、缓冲、哈希表、双向链表时间换空间：文件压缩、内存交换区（swap） 1.3 常见面试题

假设结点定义如下，请完成下列题目。

typedef struct node { int val; struct node* next; } Node;

求链表中间结点的值【leetcode 876题】

/*【示例】 int middleElement(Node* list); 输入: 1 --> 2 --> 3 输出: 2 输入: 1 --> 2 --> 3 --> 4 输出: 3 */ // 代码（C++形式） class Solution { public: ListNode* middleNode(ListNode* head) { // 快慢指针 ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } };

判断链表是否有环【leetcode 141题】

class Solution { public: bool hasCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) return true; } return false; } };

反转单链表【leetcode 206题】

/* 【示例】 Node* reverse(Node* list); 输入: 1 --> 2 --> 3 输出: 3 --> 2 --> 1 */ // 代码 // 双指针 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *cur = head; ListNode *pre = nullptr; ListNode *temp = nullptr; while (cur != nullptr) { temp = cur; cur = cur->next; temp->next = pre; pre = temp; } // delete temp; // temp = nullptr; return pre; } };

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

/* Node* mergeTwoLists(Node* list1, Node* list2); 输入：1 --> 3 --> 5 2 --> 4 --> 6 输出：1 --> 2 --> 3 --> 4 --> 5 --> 6 */ // 代码（自己的解法） class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 要求，不能额外申请堆内存空间 ListNode* cur1 = list1; ListNode* cur2 = list2; ListNode* prev1 = nullptr; // 将链表2的结点合并到链表1上 while (cur2) { if (cur1 == nullptr) { if (prev1 == nullptr) // list1为空 return list2; prev1->next = cur2; break; } else if (cur1->val > cur2->val) { // 在list1中找到了结点的插入位置 移动cur2 if (prev1 != nullptr) prev1->next = cur2; ListNode* temp2 = cur2->next; cur2->next = cur1; prev1 = cur2; // 因为插入了新结点，prev1也要改变 cur2 = temp2; } else if (cur1->val <= cur2->val){ // 在list1中没找到结点的插入位置 移动cur1 prev1 = cur1; cur1 = cur1->next; } } if (list2 != nullptr && list2->val < list1->val) return list2; else return list1; } };