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

淮南做网站郑州电力高等专科学校怎么样

淮南做网站,郑州电力高等专科学校怎么样,潍坊网站建设SEO优化熊掌号,做直播网站多少钱前言 上一节我们学习了链表的概念以及链表的实现,那么本节我们就来了解一下链表具体有什么用,可以解决哪些实质性的问题,我们借用习题来加强对链表的理解,那么废话不多说,我们正式进入今天的学习 单链表相关经典算法O…

前言

上一节我们学习了链表的概念以及链表的实现,那么本节我们就来了解一下链表具体有什么用,可以解决哪些实质性的问题,我们借用习题来加强对链表的理解,那么废话不多说,我们正式进入今天的学习

单链表相关经典算法OJ题1:移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

题目详情

题解

思路一:

要想解决这个题目,我们首先需要创建一个名为 pcur 的变量,用来遍历整个链表,找到与 val 相等的值,当我们找到了值为 val 的节点,我们不能直接释放掉这个节点,这样会导致后面的数据无法被找到,我们此时还需要定义一个变量 prev ,让 prev 一只指向 pcur 的前一个节点。当我们找到值为 val 的节点,该节点此时被 pcur 指向,我们需要用 pcur->next 来找到它的下一个节点,我们再次创建一个变量 next ,把 pcur->next 存入 next 变量中,并且把这个节点与 prev 所指向的节点连接起来,再释放掉 pcur ,此时就完成了移除链表元素的功能

思路二:

我们重新创建一个链表 newHead 和新链表的尾节点指针 newTail ,我们在原链表中进行遍历,将所有值不为 val 的节点尾插至新链表中去。

我们首先需要创建一个名为 pcur 的变量,用来遍历整个链表,若找到的值不为 val ,则直接尾插到新链表的 newTail 后面去,同时让 newTail 指针向后挪动,而 newHead 指针一直保持不变

假设我们用思路二来解决问题

我们想要完成该函数的功能,首先我们需要往函数中传入两个变量

1.链表的头节点 struct ListNode* head

2. value 的取值 int val

在开始插入的时候我们还需要判断链表当前的情况,到底是为空还是不为空

如果链表为空的话,要将 newHead 和 newTail 都赋予 pcur,此时头节点等于尾节点

如果链表不为空,newTail->next 要等于 pcur 而此时 newTail 变量要等于 newTail->next 

排查

此时我们再来考虑一下特殊情况,若是要移除的数据是链表的尾节点。

我们遍历到原链表的倒数第二个数据的时候,倒数第二个数据的 next 指针指向了尾节点,即使不插入最后一个元素到新链表中,倒数第二个节点仍然可以通过它自身的 next 指针找到原链表的尾节点,此时就会导致代码出现错误,原链表中的尾节点还是被插入到了新链表中去了

那么我们怎么才能在这种情况下不带上最后一个节点呢?

当我们找到并且尾插了倒数第二个节点的时候,我们此时把它的 next 指针赋予空指针 NULL,这样他就找不到原链表的最后一个节点了

此时我们还要考虑到一个问题,因为题目中说了,列表的节点数目可以为0,若链表的节点个数为0时,此时我们就不能把 newTail 中的 next 指针设置为空指针,这样就会造成对空指针进行解引用的问题

那么根据上述的逻辑以及注意事项的规避,我们可以写出代码如下:

typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val)
{//创建一个新链表ListNode * newHead, * newTail;newHead = newTail = NULL;//遍历原链表ListNode* pcur = head;while (pcur){//找值不为 val 的节点,然后尾插到新链表中if (pcur->val != val){//链表为空if (newHead == NULL){newHead = newTail = pcur;}//链表不为空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if (newTail)newTail->next = NULL;return newHead;
}

我们在Leetcode官网检测一下结果是否正确:

代码成功的解决问题,该题目完成

单链表相关经典算法OJ题2:反转链表

题目详情

题解

思路一:

我们可以创建一个新的链表,我们逐一的遍历原链表,让里面的每一个节点按顺序头插到新链表之中去,当遍历结束后,此时我们拿到的新链表就是反转了以后的链表

思路二:

我们先创建三个变量:分别为 n1 n2 n3。我们先让 n1 指向空指针,让 n2 指向链表的头节点,让 n3 指向 n2 的下一个节点

要完成链表的反转,我们需要按以下步骤操作:

1.先让 n2 的 next 指针不再指向 n3 ,而是让它指向 n1 (n1 初始的情况下为空指针)

2.我们再让 n1 指向 n2 ,让 n3 指向它的下一个节点

3.我们重复以上步骤,让 n2 的 next 指针不再指向 n3 ,而是让它指向 n1

4.一直重复以上步骤,当 n2 和 n3 已经找不到节点了,此时我们可以跳出循环,现在 n1 指向的位置就是反转以后链表的头节点

5.因为原题目说了,链表可以为空,所以我们还需要判断是否为空

此时我们来尝试实现代码:

typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head)
{//判空if (head == NULL){return head;}//创建三个指针ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}

提醒:最后一次让 n3 = n3->next 的代码不能够执行,因为此时 n3 已经是空指针了,不能对空指针进行解引用,所以我们需要对 n3 加以判断

我们现在在Leetcode的官网运行一下代码:

代码成功的解决问题,该题目完成

单链表相关经典算法OJ题3:链表的中间结点

题目

题解

思路一:

我们可以遍历全链表,定义一个变量 count 用来计算遍历的节点数,当遍历结束后直接返回 (count / 2)节点,则该节点就是链表的中间节点

思路二:(快慢指针)

我们首先分为奇数个偶数个两种情况

我们先定义两个变量,一个叫做 slow 指针,一个叫做 fast 指针,我们让 slow 指针每次走一步,fast 指针一次走两步,2slow = fast

1.若链表的节点数为奇数个,当 fast->next 指针指向到 NULL 指针时,此时 slow 指针刚好指向链表的中间节点

2.若链表的节点数为偶数个,当 fast 指针指向到 NULL 指针时,此时 slow 指针刚好指向链表的中间节点

有了这个思想以后,我们试着写出代码:

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) 
{//创建快慢指针ListNode* slow = head;ListNode* slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}//此时slow刚好指向中间节点return slow;}

我们在 Leetcode 的官网运行一下代码,看看结果

代码成功的解决问题,该题目完成

结尾

本节我们了解了链表在题目中的应用,下一节同样给大家细细讲解链表在题目中的应用,帮助大家更好的理解链表,那么本节的内容就到此为止了,谢谢您的浏览!!!

http://www.sczhlp.com/news/95640/

相关文章:

  • 帮建网站的人湖南株洲网站建设
  • 泰安网站开发推广wordpress flask
  • 网站开发实训结果分析及其心得体会重庆是哪个省哪个市的
  • 网站建设做网站多少钱网站开发流程图解释含义
  • 广告推广代运营公司北京seo管理
  • 在线简历制作网站免费菏泽城乡建设局官网
  • 翡翠原石网站首页怎么做wordpress编辑增强
  • 网站建设论坛fantodo网站建设与网页设计期末考试
  • js网站一键变灰青少年活动中心网站建设依据
  • 宜兴做网站多少钱风景网页制作模板
  • 做网站的用处企业网站建设应遵守的原则
  • 网站开发遇到的难题网站首屏
  • 移动端网站制作案例黄江镇网站仿做
  • 做网站负责人有法律风险吗东莞附近公司做网站建设多少钱
  • 网站小样用什么做黄骅港中远海运物流有限公司
  • 网站建设财务策划书建设银行官网首页网站购纪念币
  • php企业网站开发方案网站建设要知道的
  • 网站栏目策划 有思想的新闻wordpress群
  • P3983 赛斯石(赛后加强版)踢姐
  • 无锡 网站 seo 优化网店运营推广具体内容
  • 网站开发大赛沧州有没有做网站的
  • 网络公司网站源码下载百度站长提交工具
  • 4s店网站模板江东seo做关键词优化
  • 深圳做网站新科企业解决方案公司有哪些
  • 北京上海网站建设公司哪家好在线制作图片模板
  • 网站内容如何优化电子商务从事什么工作
  • 外贸网站建设哪里实惠惠州网站建设英语
  • 网站空间3个g多少钱什么直播可以做游戏视频网站吗
  • 宁波网站推广设计网页创意的再设计
  • 南乐网站建设电话阿里云编辑建设好的网站