详解单链表（含链表的实现过程）
目录
一，介绍单链表
二，顺序表和单链表的比较
三，单链表的实现
四，单链表例题实例
1,力扣--203，移除链表元素
2,力扣--206.反转链表
3，力扣--876,链表的中间节点
4，力扣--21,合并两个有序链表
5，环形链表的约瑟夫问题
6，力扣--分割链表
一，介绍单链表
单链表：单链表是一种在物理结构上非连续，在逻辑结构上连续的一种存储结构，也是一种线性表。
单链表的结构：
单链表由两部分构成：数据域和指针域。
数据域用来存放数据元素
指针域用来存放下一个节点的地址
二，顺序表和单链表的比较
选择建议：
使用顺序表：
1，需要频繁访问数据
2，对内存效率要求高
3，开辟的内存数量固定或者可预估
4，不需要频繁进行数据的插入和删除
使用单链表：
1，需要频繁进行数据的插入和删除
2，数据量变化大，不可预估
3，不需要随机访问
三，单链表的实现
gitee代码链接:https://gitee.com/codelsj-w/test.3.15.c.git
头文件：slt.h
源文件：slt.c
功能测试源文件：code.c
四，单链表例题实例
1,力扣--203，移除链表元素
题目：
解法思路：
创建一个新的单链表将原链表中不是val的数据尾插到新的单链表中
代码实现:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { //创建一个新的单链表 ListNode *newhead,*newtail; newhead = newtail = NULL; ListNode* pcur = head; //遍历原链表 while(pcur) { if(pcur->val != val) //不是要删除的节点，就尾插 { //如果是空链表 if(newhead==NULL) { newhead = newtail = pcur; } //如果不是空链表 else { newtail->next = pcur; newtail = pcur; } } pcur = pcur->next; } if(newhead) //初始单链表可能为空 { newtail->next = NULL; //让尾节点的下一个节点为空 } return newhead; }2,力扣--206.反转链表
题目：
解法思路：
创建三个节点n1,n2,n3，n1和n2负责反转指针，n3负责记录位置，防止丢失
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { //判空 if(head == NULL) { return head; } //创建三个指针，n1,n2用来反转链表，n3用来记录位置，防止丢失 ListNode* n1 = NULL; ListNode* n2 = head; ListNode* n3 = head->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) //最后一次n3已经为空不能访问下一个节点 { n3 = n3->next; } } return n1; }3，力扣--876,链表的中间节点
题目：
解法思路：
使用快慢指针，快指针每次走两步，慢指针每次走一步，这样当快指针走的步数一定是慢指针的两倍，当快指针走到链表的结尾时，慢指针正好走到链表的中间节点。
共有两种情况：链表的节点的数目为奇数或者偶数
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { //创建快慢指针 ListNode* slow = head; ListNode* fast = head; while(fast && fast->next) { fast = fast->next->next; //快指针每次走两步 slow = slow->next; //慢指针每次走一步 } return slow; //最后慢指针指向的就是链表的中间节点 }补充：在while(fast && fast->next) 不可交换顺序为while(fast->next && fast)
原因：当链表中节点的数目为偶数时，fast最后为NULL,此时不能再对fast进行下一个节点的查找，会直接报错。
4，力扣--21,合并两个有序链表
题目：
解法思路：
创建两个指针分别指向两个单链表的头节点，用于遍历，将节点的值进行比较，将两者的较小值尾插到新建的单链表当中。
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //判空 if(list1 == NULL) { return list2; } if(list2 == NULL) { return list1; } ListNode* l1 = list1; ListNode* l2 = list2; //创建一个新的单链表 ListNode *newhead, *newtail; //newhead = newtail = NULL; //使得头节点为一个哨兵位 newhead = newtail = (ListNode*)malloc(sizeof(ListNode)); //尾插入元素 while(l1 && l2) { if(l1->val < l2->val) { newtail->next = l1; newtail = newtail->next; l1 = l1->next; } else { newtail->next = l2; newtail = newtail->next; l2 = l2->next; } } //跳出循环时，l1或l2中一定还有元素 if(l1) { newtail->next = l1; } if(l2) { newtail->next = l2; } //动态内存的释放 ListNode* ret = newhead->next;//提前记录，防止释放后丢失 free(newhead); newhead = NULL; return ret; }5，环形链表的约瑟夫问题
题目：
解法思路：
先创建一个循环链表，再创建两个指针，一个指向头节点，一个指向尾节点，进行对链表的循环，通过计数，删除要删除的元素
代码实现：
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ typedef struct ListNode ListNode; //创建一个节点 ListNode* buyNode(int x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if(node==NULL) { exit(1); } node->val = x; node->next = NULL; return node; } //创建循环链表 ListNode* buycircle(int n) { //创建头尾节点 ListNode* head = buyNode(1); ListNode* tail = head; //创建其他节点 for(int i=2; i<=n; i++) { tail->next = buyNode(i); tail = tail->next; } //首尾相连 tail->next = head; return tail; } int ysf(int n, int m ) { ListNode* prev = buycircle(n); ListNode* pcur = prev->next; int count = 1; //当pcur的下一个元素是自己时，说明循环链表中只有这一个元素了 while(pcur->next != pcur) { //删除元素 if(count == m) { prev->next = pcur->next; free(pcur); pcur = prev->next; count = 1; //将count重新赋值为1 } else { prev = pcur; pcur = pcur->next; count++; } } return pcur->val; }6，力扣--分割链表
题目：
解法思路：
下面采用思路3进行实现
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x) { //判空 if(head == NULL) { return head; } //创建两个单链表 ListNode *lesshead,*lesstail; ListNode *greathead,*greattail; lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode)); //接收小于x的值 greathead = greattail = (ListNode*)malloc(sizeof(ListNode));//接收大于或等于x的值 //遍历原链表 ListNode* pcur = head; while(pcur) { //插入小链表 if(pcur->val < x) { lesstail->next = pcur; lesstail = lesstail->next; } //插入大链表 else { greattail->next = pcur; greattail = greattail->next; } pcur = pcur->next; } //修改大链表的尾节点的next的指向 greattail->next = NULL;//如果不加这一行，就会出现死循环 //大小链表进行连接 lesstail->next = greathead->next; return lesshead->next; }可能出现的问题：
未添加:greattail->next = NULL;
导致以下情况的死循环：
由于大链表中的5的下一个节点在原链表恰好是小链表中的元素2，导致循环时，5的下一个节点又跳转到了小链表中的2，导致无限循环（死循环 ）