网站建设现在好做吗湛江网站设计服务

当前位置： 首页 > news >正文

网站建设现在好做吗,湛江网站设计服务,自己有网站怎么做竞价,wordpress当前文章tags​ ​#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录链表OJ题(一)1. 移除…​ ​个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录链表OJ题(一)1. 移除链表元素思路一-遍历一、考虑常见情况二、考虑特殊情况1.当链表的第一个结点为待移除的结点时2.当链表的最后一个结点为待移除的结点时3.当传入链表为空时思路二-尾插法一、考虑常见情况二、考虑特殊情况1.当链表的最后一个结点为待删除的结点时2.当传入链表为空时2.当要删除所有节点时思路三-强行加上一个头结点2.总结链表OJ题(一)

1. 移除链表元素 链接203. 移除链表元素 题目描述给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例2 输入head [], val 1 输出[] 示例3 输入head [7,7,7,7], val 7 输出[] 提示 列表中的节点数目在范围 [0, 104] 内 1 Node.val 50 0 val 50 思路一-遍历 要移除链表中值为val的结点我们肯定是要将链表遍历一遍关键是我们在遍历的过程中应该如何操作。我们考虑问题的时候可以先考虑比较常见的情况再考虑特殊情况。 一、考虑常见情况 要移除某一结点也就是让该结点的前一个结点指向待移除结点的后一个结点然后将待移除结点释放即可。我们可以定义3个指针变量prevcurnext 。 prev记录待排查结点的前一个结点位置previous。 cur记录当前正在排查的结点位置current。 next记录待排查结点的后一个结点next。
   当cur指针指向的结点并非待移除的结点时3个结点依次向后移动。
   当cur指针指向待移除的结点时我们首先让prev指针指向的结点指向next然后将cur指针指向的结点释放掉
   并将next指针赋值给cur指针next指针再后移。
   如此进行下去直到链表遍历完毕那么值为val的结点也就删除了。 二、考虑特殊情况 常见情况的分析往往只能解决问题的一般情况并不能解决问题的极端情况。要真正解决问题我们需要考虑到问题的极端情况。例如当待移除的结点是第一个结点或是最后一个结点的情况当链表为空的情况。 1.当链表的第一个结点为待移除的结点时 这时我们需要先将头指针指向next然后释放cur指向的结点 并将next指针赋值给cur指针next指针再后移。
   2.当链表的最后一个结点为待移除的结点时 当排查到最后一个结点时cur指向最后一个结点next指针指向该结点指向的位置即NULL。
   我们用上面常规情况的方法对其进行分析发现常规情况的思路适用于这种特殊情况。 并且发现遍历的终止条件就是当cur为NULL的时候遍历停止。
   3.当传入链表为空时 我们可以发现若传入的链表为空链表NULLcur指针的值一开始就为空而我们遍历的终止条件就是当cur为NULL时停止遍历所以当传入链表为空时直接执行到函数末尾即返回头指针NULL。 代码实现 struct ListNode {int val;struct ListNode next; };struct ListNode removeElements(struct ListNode* head, int val) {struct ListNode* prev NULL;//记录待排查结点的前一个结点位置struct ListNode* cur head;//记录当前正在排查的结点位置while (cur ! NULL)//当cur为空时循环停止{if (cur-val val)//当前排查的结点是待移除的结点{struct ListNode* next cur-next;//记录待排查结点的后一个结点位置if (cur head)//待移除的结点是链表的第一个结点{head next;//头指针指向nextfree(cur);//释放第一个结点cur next;//将next指针赋值给cur指针}else//待移除的结点不是链表的第一个结点{prev-next next;//prev指针指向的结点指向nextfree(cur);//将cur指针指向的结点释放掉cur next;//将next指针赋值给cur指针}}else//当前排查的结点不是待移除的结点{prev cur;//指针后移cur cur-next;//指针后移}}return head;//返回新的头指针 }思路二-尾插法 一、考虑常见情况 还可以通过遍历原链表将不是val的值尾插到新链表newHead这时删第一个也没有什么影响,转换成尾插的思路。 定义一个尾指针tail第一次尾插需要赋值newHeadtailcur cur-val!val,尾插进新链表再更新tailtail-nextcurtailtail-next
   cur-valval,提前保存下一个节点释放cur将下一个赋值给cur 最后返回newHead 二、考虑特殊情况 1.当链表的最后一个结点为待删除的结点时 在删除最后一个6的时候上一个节点tail5的next还指向6删除后就指向野指针了所以需要tail-nextNULL
   但如果最后一个为7,便会拿下来尾插tail-nextNULL这时不会出现野指针
   那综合上面两种情况不如直接置空(tail-nextNULL)吧。但运行后发现还是有问题
   2.当传入链表为空时 在链表为空时循环根本不会进入所以还要加一个链表为空的判断if(headNULL)直接return NULL不删除了。但运行后发现还是有问题
   2.当要删除所有节点时 若链表全是7的时候这时所以节点都被删了没有节点尾插了newHead和tail还是空又出现了野指针所以干脆不判断链表为空而是判断tail是否为空若不为空tail-nextNULL * Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode next; };/ struct ListNode removeElements(struct ListNode* head, int val) {struct ListNode*newHeadNULL,*tailNULL;struct ListNode*curhead;while(cur){if(cur-val!val){//尾插if(tailNULL){newHeadtailcur;}else{tail-nextcur;tailtail-next;}curcur-next;}else{struct ListNode*nextcur-next;free(cur);curnext;}}if(tail)tail-nextNULL;return newHead; }思路三-强行加上一个头结点 我们可能觉得思路一的代码比较复杂当我们要移除某一个结点时还需要判断该结点是否为第一个结点那么有没有什么办法可以不用进行这一步操作呢 回答是肯定的。办法就是在传入的链表前面强行加上一个头结点并让链表原来的头指针指向该头结点这样我们就不用判断待移除的结点是否为第一个结点了因为现在第一个结点是头结点。
   在加了头结点后我们就只需要根据常见情况的逻辑进行代码的编写即可。但是有一点不能忘记就是在遍历完链表后要将头结点指向的位置即第一个结点的位置赋值给头指针并将头结点释放掉最后才能返回头指针。 代码实现 struct ListNode {int val;struct ListNode next; }; struct ListNode removeElements(struct ListNode* head, int val) {struct ListNode* guard (struct ListNode)malloc(sizeof(struct ListNode));//申请一个头结点返回其地址guard-next head;//让头结点指向链表的第一个结点struct ListNode cur guard-next;//cur指针指向原链表第一个结点struct ListNode* prev guard;//prev指针指向头结点while (cur ! NULL)//当cur为空时循环停止{if (cur-val val)//当前排查的结点是待移除的结点{struct ListNode* next cur-next;//记录待排查结点的后一个结点位置prev-next next;//prev指针指向的结点指向nextfree(cur);//将cur指针指向的结点释放掉cur next;//将next指针赋值给cur指针}else//当前排查的结点不是待移除的结点{prev cur;//指针后移cur cur-next;//指针后移}}head guard-next;//将头结点指向的位置赋值给头指针使头指针指向链表第一个结点free(guard);//释放头结点guard NULL;//及时置空return head;//返回新的头指针 }2.总结 今天我们通过三种思路分析并完成移除链表元素这道链表OJ题目。总体来说思路三会相较于前两个思路减少踩坑但若是第一次遇见也很难想到。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~