做网站实训总结,查看网站建设的特点,广州设计网站公司,wordpress昵称中文欢迎各位来到 Harper.Lee 的学习小世界#xff01; 博主主页传送门#xff1a;Harper.Lee的博客主页 想要一起进步的uu可以来后台找我交流哦#xff01; 在DS#xff1a;单链表的实现 和 DS#xff1a;顺序表的实现这两篇文章中#xff0c;我详细介绍了顺序表和单链表的… 欢迎各位来到 Harper.Lee 的学习小世界 博主主页传送门Harper.Lee的博客主页 想要一起进步的uu可以来后台找我交流哦 在DS单链表的实现 和 DS顺序表的实现这两篇文章中我详细介绍了顺序表和单链表的实现方法及其相关注意点uu们可以点击跳转学习。俗话说“光说不练假把式”下面我们通过几道经典OJ算法题来进行顺序表和单链表的相关训练
一、力扣--203. 移除链表元素 题目给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回新的头节点 。 思路1遍历原链表将值为val的节点释放掉很像单链表中删除指定位置的节点。 思路2找值不为val的节点将其尾插到不带头的新链表中返回该新链表的头节点。 创建的结构体指针newHead和newTail均指为空。改变的是newTail而不是newHead。 a. 创建链表的第一个节点从原链表第一个节点开始判断该节点的值如果不是val那么他就是新链表第一个节点newHead从第一个节点开始创建新链表相当于是头插同时也是尾插; b. 其余节点依次进行遍历并判断节点的值是否为val如果是就进行释放操作 如果不是就尾插入新链表中用newTail来接收 c. 遍历链表使用pcur。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;//说明该结构体中的内容但是如果要使用该结构体,就需要struct ListNode来定义结构体太麻烦所以重命名 * };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建一个新链表ListNode* newHead,*newTail;//????newHead newTailNULL;//遍历原链表ListNode* pcur head;//head是传进来的参数结构体指针while(pcur)//pcur用来遍历链表{//找值不为val的节点尾插到新链表。if(pcur-val!val){//链表为空if(newHeadNULL){newHeadnewTailpcur;//插入的第一个节点既是头节点也是尾节点}//链表不为空else{//newtail的下一个位置插入数据newTail-nextpcur;newTailnewTail-next;}}pcurpcur-next;//pcur往下走继续遍历}if(newTail)newTail-next NULL;//newTail的next指针要置为空return newHead;
}
二、力扣--206. 反转链表 题目描述给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路1创建一个新链表newHead和newTail从第一个节点作为newTail且不再改变开始遍历原链表同时将原链表的节点利用头插法建立该新链表。 思路2创建3个指针完成原链表的翻转 。
/*** Definition for singly-linked list.* struct ListNode {* int val;//已知存储的数据和指向下一个节点的指针* struct ListNode *next;* };*/typedef struct ListNode ListNode;//将结构体指针struct ListNode重命名为ListNode
struct ListNode* reverseList(struct ListNode* head) {//先判断链表是否为空if(headNULL){return head;}//创建三个指针n1 n2 n3 让n2的next指向n1//n1 n2,n2 n3,n3 n3-nextListNode* n1, *n2,*n3;n1 NULL,n2 head;n3 n2-next;//初始化三个指针n2指向n3while(n2){//先反转方向再n1n2; n2n3;n3n3-next;n2-nextn1; //n2的next指针指向n1n2;n2n3;if(n3)//n3 走到为空了不能继续走也就是不能解引用了n3n3-next;}return n1;//因为链表的接待有数据范围所以说明链表 可能为空n3 n2-next可能不合适
}
三、力扣--21. 合并两个有序链表 题目描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 从前往后找小数据数据会丢失所以从后往前找大数据.
第一个版本的代码会报错
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode* l1 list1;ListNode* l2 list2;//创建新链表ListNode* newTail,*newHead;newHead newTail NULL;while(l1 l2)//使用 因为两个要同时满足非空链表 {if(l1-vall2-val)//开始比较存储的值的大小{//l1拿下来进行尾插if(newHead NULL)//头节点为空{newHeadnewTaill1;}else{//新链表不为空newTail-nextl1;newTailnewTail-next;}l1l1-next;//原来的链表也要继续往前遍历}else{//l2拿下来尾插if(newHeadNULL){newHeadnewTaill2;}else{newTail-nextl2;newTailnewTail-next;}l2l2-next;}}//跳出循环面临两种情况l1走到空 或者 l2走到空上下一个节点止咳尾插不用再比较了if(l2)//l2不为空{newTail-next l2;}if(l1){newTail-next l1;}return newHead;
}
1、 报错
分析报错具体原因 如果list1为空链表l1也为空不能进入while循环所以来到跳出while循环的 if 部分。l2不为空执行 newTail-next l2; 但是因为没有进入while循环所以新链表也无法在while循环中创建节点也就是说新链表仍然时空连而此刻 newTail-next 操作 相当于对空指针进行解引用操作。因而报出上图所示错误。
解决办法链表为空有一个提示说明链表可能同时为空。根据提修改代码判断链表为空的情况做另外的处理。 首先链表是已经排为升序了的如果其中一个链表为空可直接返回里另外一个链表如果两个链表都为空那么就直接返回NULL。先增加判断链表是否为空的情况。
第二个版本代码正确代码如下:
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* newTail,*newHead;newHead newTail NULL;while(l1 l2)//使用 因为两个要同时满足非空链表 {if(l1-vall2-val)//开始比较存储的值的大小{//l1拿下来进行尾插if(newHead NULL)//头节点为空{newHeadnewTaill1;}else{//新链表不为空newTail-nextl1;newTailnewTail-next;}l1l1-next;//原来的链表也要继续往前遍历}else{//l2拿下来尾插if(newHeadNULL){newHeadnewTaill2;}else{newTail-nextl2;newTailnewTail-next;}l2l2-next;}}//跳出循环面临两种情况l1走到空 或者 l2走到空上下一个节点止咳尾插不用再比较了if(l2)//l2不为空{newTail-next l2;}if(l1){newTail-next l1;}return newHead;
}
2、存在重复代码如何优化代码 在上面的代码中观察发有一段重复出现的代码将节点拿下来进行尾插处理。我们将这部分代码进行优化处理。一种优化方法是函数封装。此外还可以进行
代码重复的原因新链表存在空链表和非空链表两种情况。
解决思路让新链表不为空。
解决办法之前的newTaail和newHead是将其创建为空NULL现在为它动态申请一块内存 newHead newTail NULL; 改成newHead newTail (ListNode*)malloc(sizeof(ListNode)); 动态申请空间但是不存储任何数据。此时链表不为空头尾指针都指向一个有效的地址节点。然后将while循环中判断链表是否为空的代码删掉
删除如下注释
//while循环中删除判断部分 while(l1 l2)//使用 因为两个要同时满足非空链表 {if(l1-vall2-val)//开始比较存储的值的大小{//l1拿下来进行尾插//if(newHead NULL)//头节点为空//{//newHeadnewTaill1;//else{//新链表不为空newTail-nextl1;newTailnewTail-next;// }l1l1-next;//原来的链表也要继续往前遍历}else{//l2拿下来尾插//if(newHeadNULL)//{//newHeadnewTaill2;// }// else// {newTail-nextl2;newTailnewTail-next;// }l2l2-next;}} 3、 注意此时不能或者直接返回newHead因为最后得到的链表多了一部分这一部分是因为系统随机给动态申请的空间赋随机值。因此要返回不包含此部分的链表。return newHead-next;最后的链表如下图所示 4、此外动态内存申请的空间都是要释放掉的而这里没有释放操作但不会报错是因为我们写的程序需要提交到力扣服务端进行运行后会自动释放。但是如果是我们自己写代码为了养成好的空间开辟习惯记得释放空间。如果直接 free(newHead); 这样就找不到原来的空间了也就不能通过return newHead-next;将最终结果返回了。因此利用结构体指针ret记录空间然后再释放返回ret。
最终代码如下
/*** 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) {//判断链表是否为空//newHead newTail NULL;newHead newTail (ListNode*)malloc(sizeof(ListNode));ListNode* l1 list1;ListNode* l2 list2;//创建新链表ListNode* newTail,*newHead;// newHead newTail NULL;newHead newTail (ListNode*)malloc(sizeof(ListNode));//动态申请空间但是不存储任何数据 while(l1 l2)//使用 因为两个要同时满足非空链表 {if(l1-vall2-val){newTail-nextl1;newTailnewTail-next;l1l1-next;//原来的链表也要继续往前遍历}else{newTail-nextl2;newTailnewTail-next;l2l2-next;}}if(l2)//l2不为空{newTail-next l2;}if(l1){newTail-next l1;}ListNode* ret newHead-next;free(newHead);newHead NULL;return ret;
} 5、刚动态申请空间的那部分节点没有存入数据它实际是链表分类中的一种叫做带头链表。头节点叫做哨兵位只起站岗的作用没有任何有效意义。
此题和之前的合并两个有序数组有点相似。 四、力扣--876. 链表的中间节点 题目描述给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 思路一count 记录节点数直接返回count/2节点的next节点 思路二 创建指针数组用来记录每一次遍历的数组然后长度除以对应的数组的指针就是中间节点。 思路三快慢指针法。奇数个节点slow每次走一步fast每次走两步重复这个操作直到fast-nextNULL时停止此时slow指向的就是中间节点偶数个节点slow每次走一步fast每次走两步重复这个操作直到fastNULL时停止此时slow指向的就是中间节点。即使链表很长好此方法也可以因为对链表只需遍历一遍。其中的原理在于满足2slowfast。 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode* slow head;ListNode* fast head;while(fast fast-next)//fast和fats-next不能交换位置//如果链表是在有欧束个节点的情况下fast的最后一次会直接走到空fast-next就是对其进行解引用操作-相当于解引用操作符{slowslow-next;fastfast-next-next;}//此时slow指向的就是中间节点return slow;
}
1、循环条件可以进行交换吗 循环条件while(fast fast-next)其中循环条件不能进行交换否则会出现链表为偶数个节点的情况下fast走到头时fast NULL已经满足了fast-next为空空指针解引用报错的情况。
2、快慢指针总结 慢指针每次走一步快指针每次走两步慢指针*2 快指针。快指针遍历完一遍链表时快指针在链表的中间位置 。如果链表的节点有偶数个fastNULL如果链表的节点是奇数个fast-nextNULL。
五、牛客--环形链表的约瑟夫问题
循环链表的经典应用 背景著名的Josephus问题 据说著名犹太历史学家Josephus有过以下的故事在罗⻢⼈占领乔塔帕特后39个犹太⼈与 Josephus及他的朋友躲到⼀个洞中39个犹太⼈决定宁愿死也不要被⼈抓到于是决定了⼀个⾃杀⽅式41个⼈排成⼀个圆圈由第1个⼈开始报数每报数到第3⼈该⼈就必须⾃杀然后再由下⼀个重新报数直到所有⼈都⾃杀⾝亡为⽌。 然⽽Josephus?和他的朋友并不想遵从Josephus要他的朋友先假装遵从他将朋友与自己排在第16个与第31个位置于是逃过了这场死亡游戏。 详细分析过程如下图片所示第一次 尝试传入手写笔记照片可能效果不太理想 创建代还链表的过程 首先创建第一个节点该节点既是phead也是ptail然后继续创建节点并将之前先创建的节点与该节点连接在一起ptail ptail-next;,直到最后一个节点连接进去。 但此时还没有形成带环链表加上 ptail-next phead; 头尾相连链表成环。 代码如下
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param n int整型 * param m int整型 * return int整型*/#include stdlib.h
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* creatCircle(int n)
{//先创建第一个节点ListNode* phead buyNode(1);//第一个节点存储数据1ListNode* ptail phead;//ptail用来尾插for(int i 2;i n;i){ ptail-next buyNode(i);//将新创建的节点与链表连接在一起ptail ptail-next;//ptail也要继续前进}ptail-next phead;//首尾相连链表成环//return 的方法return ptail;//不返回phead而是返回ptail
}
int ysf(int n, int m ) {//1. 根据n创建带环链表ListNode* prev creatCircle(n);//这三句代码就是图片中重复操作的那部分过程ListNode* pcur prev-next;int count 1;//初始时count为1因为前面一句代码中pcur指向了第一个节点就需要报数//开始报数//当链表只有一个节点时 跳出循环最后一个节点的next指向它自己while(pcur-next ! pcur)//当链表只有最后一个节点且指向它自己时循环结束{if(count m){//销毁pcur节点首先prev改变指向prev-next pcur-next;free(pcur);//此时pcur是野指针pcur prev-next;count 1;}else{//此时不需要销毁节点因为报数不是m不需要销毁prev pcur;pcur pcur-next;count;}}//此时剩下的一个节点就是要返回的节点里的值return pcur-val;
} 1、末尾return之前为了养成良好的代码习惯可以先把pcur原来的值val存储下来然后将pcur节点释放掉。 2、创建环形链表时要返回链表的 ptail 尾节点。 return 头节点还是尾节点要看需要如何使用该链表。首先phead报数为1然后phead的后一个节点指针 ptail 这个过程需要用到ptail需要走到phead的前面。按照这个过程则需要返回ptail。
六、力扣--02.04 面试题分割链表 题目描述给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。 注意这不是排序而是分割链表不需要保证 x 两边节点的相对位置。 思路1在原链表上进行修改。若pcur节点的值小于x往前走若pcur节点的值大于或者等于x尾插在原链表后面删除旧节点。 思路2在带头新链表newHead和newTail上进行修改。若pcur节点的值小于x节点头插在新链表中若pcur节点的值大于或者等于x将节点尾插在新链表中。 思路3创建两个新链表大链表greaterHead和greaterTail和小链表lessHead和额lessTail。 小于x的节点就尾插入小链表大于等于x的节点就尾插入大链表中。然后将小链表的尾节点和大链表的首尾相连合并小链表和大链表
/*** 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* greaterHead,*greaterTail;lessHead lessTail (ListNode*)malloc(sizeof(ListNode));greaterHead greaterTail (ListNode*)malloc(sizeof(ListNode)); //遍历原链表将原链表中的节点尾插到大小链表中ListNode * pcur head;while(pcur){if(pcur-val x){//尾插到小链表中lessTail-next pcur;lessTail lessTail-next;}else{greaterTail-next pcur;greaterTail greaterTail-next;}pcur pcur-next;}//小链表的尾节点和大链表的第一个有效的节点首尾相连lessTail-next greaterHead-next;greaterTail-next NULL;//从小链表的第一个有效节点开始返回,返回之前动态申请的空间还需要释放掉ListNode* ret greaterHead NULL;free(lessHead);free(greaterHead);lessHead greaterHead NULL;return ret;
} 创作不易喜欢的uu支持一下哦
