hello，大家好，本文学习单链表及其基本操作，话不多说，直接开讲吧
单链表定义
单链表是一种链式存取的数据结构，数据元素的逻辑顺序通过指针链接，下图为单链表的结构示意图。
下述代码为C语言下定义的节点结构
struct LinkList{int val;char name[40];struct LinkList *next;};
单链表的插入
单链表的插入方式有头插法与尾插法两种，首先介绍头插法。
单链表头插法
下图为单链表头插法示意图，我们将新数据插入到单链表的头部位置。
头插法的代码如下：
/* 单链表头插法 */void insertHead(struct LinkList **head){struct LinkList *list, *temp;list = (struct LinkList *)malloc(sizeof(struct LinkList));if(list == NULL){printf("哦豁，内存分配失败了\n");exit(1);}getInput(list);if(*head == NULL){ // 单链表为空*head = list;list->next = NULL;}else{temp = *head;*head = list;list->next = temp;}}/* 获取用户输入的节点数据 */void getInput(struct LinkList *list){printf("请输入姓名：");scanf("%s", list->name);printf("请输入学号：");scanf("%d", &list->val);}/* 打印单链表数据信息 */void printLinkList(const struct LinkList *head){const struct LinkList *temp = head;while(temp != NULL){printf("姓名：%s\t学号：%d\n", temp->name, temp->val);temp = temp->next;}}/* 释放堆空间 */void freeLinkList(struct LinkList **head){struct LinkList *temp;while(*head != NULL){temp = *head;*head = (*head)->next;free(temp);temp = NULL;}}
需要注意的是，head是指向第一个节点的指针，插入元素需要修改head本身的值，因此参数传递时，需要将head的地址作为参数传递，也即此时参数类型为" struct LinkList ** "；此外，堆空间申请的内存需要及时释放以防止内存泄漏。下图为上述头插法示例程序的执行结果：
单链表尾插法
顾名思义，单链表的尾插法则是每次将新加入的数据添加到单链表的尾部，下图为尾插法示意图。
尾插法代码如下：
void insertTail(struct LinkList **head){static struct LinkList *tail; // 引入哨兵节点struct LinkList *list;list = (struct LinkList *)malloc(sizeof(struct LinkList));if(list == NULL){printf("哦豁，内存分配失败了\n");exit(1);}if(*head == NULL){ // 单链表为空*head = list;list->next = NULL;}else{tail->next = list;list->next = NULL;}tail = list; // 更新tail节点位置}
在使用单链表尾插法时，为防止每次新插入数据时遍历得到尾节点，我们定义一个静态哨兵节点，使其一直指向单链表的尾部节点，这样可以大大提升尾插法的效率。下图为上述程序的运行结果：
单链表的查找
本文以给定待查找的姓名为例进行演示，代码如下：
struct LinkList *serchLinkList(struct LinkList *head, char *name){struct LinkList *node = head;while(node != NULL){if(!strcmp(node->name, name)){break;}cur = cur->next;}return cur;}
上述代码的运行结果如下：
单链表的删除
单链表的删除节点操作也就是指针操作，首先修改待删除节点的上一节点指针，使其指向待删除节点的下一节点，然后释放删除节点的空间即可，代码描述如下：
void deleteNode(struct LinkList **head, int flag){struct LinkList *cur, *pre;cur = *head, pre = NULL;while(cur && cur->val != flag){pre = cur;cur = cur->next;}if(cur == NULL){printf("找不到对应节点\n");return ;}else{if(pre == NULL){ // 待删除节点为头节点*head = cur->next;}else{pre->next = cur->next;}free(cur);cur = NULL;}}
下图为上述程序运行结果：
单链表反转
单链表反转为经典的双指针问题，实现代码如下：
struct LinkList *reverseLinkList(struct LinkList **head){struct LinkList *cur, *pre; // 定义两个指针// cur指针指向头节点，pre指针指向cur的上一节点cur = *head, pre = NULL;while(cur != NULL){//临时变量保存cur的下一节点struct LinkList *temp = cur->next;// cur节点的next指针指向前一节点cur->next = pre;// pre指针与cur指针分别前移pre = cur, cur = temp;}return pre;}
上述链表反转的运行结果如下：
后记
本文讲述了单链表最基本的一些操作，在实际应用中仍存在诸多其他有关单链表的操作，例如两两交换链表节点以及K个一组翻转链表等等，建议大家在LeetCode网站上多多练习。
另外有关单链表的算法，有以下几点建议：
善用哨兵节点简化实现难度，例如在尾插法实现时，定义哨兵节点指向链表的尾节点，可降低算法的时间复杂度
善于画图思考，将指针的链接逻辑清晰化，厘清链表结构，防止指针丢失与内存泄漏
讲完啦，欢迎读者留言，无论是文章勘误亦或是有关文章内容的讨论与建议，都欢迎，谢谢大家。
