【数据结构】链表相关题目(简单版)
创始人
2024-05-31 06:24:41
0

在这里插入图片描述

🚀write in front🚀
📜所属专栏: 初阶数据结构
🛰️博客主页:睿睿的博客主页
🛰️代码仓库:🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!!
关注我,关注我,关注我你们将会看到更多的优质内容!!

在这里插入图片描述

文章目录

  • 前言
    • 习题1:
    • 习题2
    • 习题3
      • 衍生题1:
      • 衍生题2:
    • 习题4:
    • 习题5:
  • 总结

前言

  在学完了顺序表的基本知识后,我们可以通过一些习题来巩固所学知识!

习题1:

删除链表中等于给定值 val 的所有结点。oj链接
在这里插入图片描述
这道题目有两种做法:

  • 方法一:双指针的遍历,通过双指针来查找删除节点并连接后面的节点,但是缺点就是会有特殊情况需要考虑(头删的情况),代码如下:
    在这里插入图片描述
  • 方法2:通过遍历,将节点尾插到新链表,最后返回新链表,代码如下:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*cur=head,*newnode=NULL,*tail=NULL;while(cur){if(cur->val!=val){if(newnode==NULL){newnode=cur;tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode*next=cur;cur=next->next;free(next);}}
if(tail)
{tail->next=NULL;
}return newnode;
}

习题2

反转一个单链表。oj链接
在这里插入图片描述
这道题也有两种方法,

  • 方法1:用三指针的方法,前两个来改变每个节点的链接关系,最后一个节点用来标记位置方便遍历链表
    在这里插入图片描述
    代码如下:
    在这里插入图片描述
  • 方法2:取每个节点头插到新链表:

在这里插入图片描述

习题3

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。oj链接
在这里插入图片描述
  这里我们就要介绍一下快慢指针了。通过快慢指针我们可以解决很多问题,以后都会用到。
  那么什么是快慢指针呢?
  顾名思义,快慢指针就是通过两个不同指针步长的不同来遍历链表。
在这里插入图片描述
  这道题我们让一个指针走两步,一个指针走一步,当快指针指向空或快指针的next指向空的时候,慢指针指向位置就是中间节点位置。

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*slow=head,*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}

衍生题1:

输入一个链表,输出该链表中倒数第k个结点。oj链接
在这里插入图片描述
  其实也是快慢指针的思想,只是这里不是步长的不同,而是起点不同:
  要寻找倒数第k个节点,就让快指针的起点在慢指针的后k步。当快指针指向空的时候,慢指针就指向倒数第k个节点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode* slow=pListHead;struct ListNode* fast=pListHead;while(k--){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

衍生题2:

给定一个链表,判断链表中是否有环。oj链接
在这里插入图片描述
  这道题也是用快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。比如:陪女朋友到操作跑步减肥。

  那么,为什么快指针每次走两步,慢指针走一步可以?
  假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。
  此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
代码如下:

bool hasCycle(struct ListNode *head) 
{struct ListNode*fast=head,*slow=head;if(head==NULL||head->next==NULL){return false;}fast=fast->next;while(fast!=slow){if(fast==NULL||fast->next==NULL)break;fast=fast->next->next;slow=slow->next;}if(fast==slow)return true;return false;
}

习题4:

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的oj链表

  这道题引入了哨兵位,也就是空的头节点。其实,对于链表尾插的时候,需要判断是否为空,比较麻烦,只要我们创建一个空的头节点就可以避免很多情况。

  链表在头插的时候我们不需要头节点;
  链表在尾插的有空的头节点会更方便。
在这里插入图片描述

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*tail=newnode;tail->next=NULL;while(list1&&list2){if(list1->valval){tail->next=list1;tail=list1;list1=list1->next;}else{tail->next=list2;tail=list2;list2=list2->next;}}if(list1)tail->next=list1;
if(list2)tail->next=list2;return newnode->next;
}

习题5:

编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。oj链接

在这里插入图片描述
  这道题我们创建两个新链表(带有哨兵位的空头节点),小于的尾插到一个链表,大于的尾插到另外一个链表,最后将他们连起来即可。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode*greaternode=NULL;struct ListNode*lessnode=NULL,*cur=pHead;struct ListNode* gtail=greaternode,*ltail=lessnode;while(cur!=NULL){if(cur->val>=x){gtail->next=cur;gtail=cur;cur=cur->next;gtail->next=NULL;}else{ltail->next=cur;ltail=cur;cur=cur->next;ltail->next=NULL;}}ltail->next=greaternode->next;return lessnode->next;}
};

总结

  还是那句话,数据结构需要多画图,并且对各种情况要有十足的把握才能做对题目。
  更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

专栏订阅:
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

在这里插入图片描述

相关内容

热门资讯

王者定位怎么关安卓系统,轻松实... 你是不是也和我一样,对王者荣耀这款游戏爱得深沉呢?不过,有时候游戏里的设置让人头疼,比如安卓系统的王...
树莓派安卓系统流畅,打造便携式... 亲爱的读者们,你是否曾想过,将树莓派与安卓系统结合,会擦出怎样的火花呢?今天,就让我带你一起探索这个...
安卓系统智能机顶盒,引领家庭娱... 你有没有想过,家里的电视也能变得智能起来?没错,就是那个陪伴我们多年的老电视,现在也能摇身一变,成为...
安卓系统很差了吗现在,性能优劣... 最近是不是有不少朋友在讨论安卓系统的问题呢?有人说它越来越差了,也有人觉得它还是那个熟悉的“老朋友”...
安卓系统uc安装包,Andro... 你有没有发现,手机里的安卓系统越来越强大了?今天,咱们就来聊聊这个话题——安卓系统中的UC安装包。你...
安卓系统谷歌能删吗,谷歌能否删... 你有没有想过,那个一直陪伴你手机生活的安卓系统,它背后的谷歌爸爸,是不是也能被你随意删掉呢?这可不是...
安卓系统会不会更耗电,解析其功... 你有没有发现,手机用着用着,电池就有点不给力了?尤其是那些用安卓系统的手机,有时候感觉电就像流水一样...
安卓系统中无效目录,安卓系统无... 你有没有遇到过在安卓系统中,明明文件夹就在那里,但是就是找不到的情况?别急,今天就来给你揭秘安卓系统...
国产安卓机哪个系统好用,探寻最... 你有没有想过,国产安卓机哪个系统最好用呢?这可是个让人纠结的问题,毕竟每个系统都有它的特色和亮点。今...
安卓系统cpua9,引领性能与... 你有没有发现,最近你的安卓手机运行得是不是比以前顺畅多了?这可多亏了那个强大的安卓系统CPUA9啊!...
安卓系统usb驱动程序,功能、... 你有没有遇到过这种情况:手机里存了那么多宝贝照片和视频,想传输到电脑上保存,结果电脑却像个小顽皮,死...
安卓操作系统怎么关闭,轻松关闭... 手机里的安卓操作系统是不是有时候让你觉得有点儿烦呢?别急,今天就来手把手教你如何轻松关闭安卓操作系统...
追星手机壳推荐安卓系统,盘点热... 你有没有发现,现在追星族们对手机壳的热爱简直到了疯狂的地步?没错,就是那种能让你一秒变身偶像迷妹的手...
ios系统用安卓系统游戏下载软... 你有没有想过,明明是iOS系统的手机,却想玩安卓系统的游戏?这可不是什么天方夜谭,现在就有这么神奇的...
安卓高系统怎么用美化,打造专属... 亲爱的安卓用户们,你是不是也和我一样,对手机系统美化情有独钟呢?想要让你的安卓手机焕然一新,变得个性...
安卓系统怎么开夜间模式,安卓系... 亲爱的手机控们,你是不是在夜晚使用安卓手机时,眼睛感到有些不适?别担心,今天我要给你揭秘一个超级实用...
王者安卓系统用苹果人脸,一场视... 你知道吗?最近在手机圈里可是掀起了一股不小的波澜呢!那就是王者安卓系统竟然用上了苹果人脸识别技术!是...
安卓444怎么升级系统,轻松迈... 你那安卓444的小家伙是不是已经有点儿落伍了?别急,今天就来给你详细说说怎么给它来个系统升级,让它焕...
安卓系统raw修图软件,探索安... 你有没有发现,手机拍照越来越方便了,但有时候拍出来的照片还是不够完美呢?别急,今天就来给你安利几款安...
安卓系统的王者切换苹果,从安卓... 你知道吗?最近身边的朋友圈里掀起了一股热潮,那就是安卓系统的王者们纷纷切换到苹果阵营。这可真是让人大...