链表（C语言版）

链表

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

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

链表的分类：

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

1.1 单链表

基本操作

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

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

3. 查找

   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 - 1Node* 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 底层的数据结构都是双向链表。

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

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

2. 删除（可以当前结点）

3. 查找

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

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

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

• 空间换时间：缓存、缓冲、哈希表、双向链表
• 时间换空间：文件压缩、内存交换区（swap）

1.3 常见面试题

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

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

1. 求链表中间结点的值【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;}
   };

2. 判断链表是否有环【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;}
   };
   

3. 反转单链表【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;}
   };
   

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

   /* Node* mergeTwoLists(Node* list1, Node* list2);
   输入：1 --> 3 --> 52 --> 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中找到了结点的插入位置 移动cur2if (prev1 != nullptr)prev1->next = cur2;ListNode* temp2 = cur2->next;cur2->next = cur1;prev1 = cur2; // 因为插入了新结点，prev1也要改变cur2 = temp2;}else if (cur1->val <= cur2->val){ // 在list1中没找到结点的插入位置 移动cur1prev1 = cur1;cur1 = cur1->next;}}if (list2 != nullptr && list2->val < list1->val)return list2;else return list1;}
   };