详解单链表（含链表的实现过程）

目录一介绍单链表二顺序表和单链表的比较三单链表的实现四单链表例题实例​​​​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(newheadNULL) { newhead newtail pcur; } //如果不是空链表 else { newtail-next pcur; newtail pcur; } } pcur pcur-next; } if(newhead) //初始单链表可能为空 { newtail-next NULL; //让尾节点的下一个节点为空 } return newhead; }2,力扣--206.反转链表题目解法思路创建三个节点n1,n2,n3n1和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(nodeNULL) { exit(1); } node-val x; node-next NULL; return node; } //创建循环链表 ListNode* buycircle(int n) { //创建头尾节点 ListNode* head buyNode(1); ListNode* tail head; //创建其他节点 for(int i2; in; 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导致无限循环死循环