位置: IT常识 - 正文

【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点(iterator用法 移除对象)

编辑:rootadmin
【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点

推荐整理分享【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点(iterator用法 移除对象),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:iterator移除元素,list 移除,移除list1中所选中的项目,iterator移除元素,list移除一个指定元素,移除list1中所选中的项目,移除list1中所选中的项目,leetcode移除元素,内容如对您有帮助,希望把文章链接给更多的朋友!

目录

一.【Leetcode203】移除链表元素

1.链接

2.题目再现

 A.双指针法

B.类尾删法

C.哨兵位

二.【Leetcode876】链表的中间节点

1.链接:链表的中间节点

2.题目再现

3.解法:快慢指针

三.链表中倒数第k个节点

1.链接:链表中倒数第k个节点

2.题目再现

3.解法 :快慢指针


一.【Leetcode203】移除链表元素1.链接

移除链表元素

2.题目再现

 A.双指针法

1.创建一个指针 cur=head  和一个指针  pre=NULL;  

2.用cur->val 与 val 比较,如果不相等则把 cur 赋给 pre 使cur 指向下一个节点,即

   cur=cur->next;

3.如果相等则使 pre 的 next 指向 cur 的 next ,即:

 pre->next=cur->next ,然后再 free 掉 cur ,最后再使 cur 等于 pre 的 next,注意在进行这些步骤之前要判断 pre 是否为空 ,若为空即为头删;

演示:

双指针

代码:

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*pre=NULL; struct ListNode*cur=head; while(cur) { if(cur->val!=val) { pre=cur; cur=cur->next; } else { if(pre==NULL) { head=cur->next; free(cur); cur=head; } else { pre->next=cur->next; cur=pre->next; } } } return head;}B.类尾删法

1.创建一个新的指针newhead ,同时为了省去找尾的麻烦,我们可以定义一个尾指针 tail 来保存尾节点;

2.再创建一个指针 cur =head ,用来遍历链表;

3.如果 cur->val != val ,则尾插 ,注意要判断 tail 是否为空 ,类似于单链表的尾插那部分,如果不理解的话,可查看文章 :单链表的增删查改;

4.如果 cur->val ==val,则 cur=cur->next ;

5.最后要将尾节点置空。

演示:

类尾插

代码:

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode *newhead=NULL; struct ListNode*tail=NULL; struct ListNode*cur=head; while(cur) { if(cur->val!=val) { if(tail==NULL) { newhead=tail=cur; } else { tail->next=cur; tail=tail->next; } cur=cur->next; } else { cur=cur->next; } } if(tail) { tail->next=NULL; } return newhead;}C.哨兵位

1.malloc 一个哨兵位节点 dummyhead,使其 next 指向 head ;

2.再定义一个节点 tmp = dummyhead ,用这个遍历链表;

【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点(iterator用法 移除对象)

3.注意因为 tmp ->next 才是 head ,所以 while 里要写 tmp->next !=NULL

演示:

移除链表元素 哨兵位法动态演示

代码:

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode)); dummyhead->next=head; struct ListNode*tmp=dummyhead; while(tmp->next!=NULL) { if(tmp->next->val==val) { tmp->next=tmp->next->next; } else { tmp=tmp->next; } } return dummyhead->next;}二.【Leetcode876】链表的中间节点1.链接:链表的中间节点2.题目再现

3.解法:快慢指针

1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head;

2.遍历链表,快指针一次走2步,慢指针一次走1步 ;

3.注意:因为链表的长度可能是单数也可能是双数,所以当我们已 fast 是否为NULL 作为循环控制条件的话,要在 fast 走2步前判断 fast->next 是否为空;

4.最后慢指针就是中间节点。

演示:

链表中间节点 快慢指针动态演示

代码:

struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow=head; struct ListNode*fast=head; while(fast) { if(fast->next==NULL) //注意判断 { break; } else { fast=fast->next->next; //fast 走2步 } slow=slow->next; //slow 走1步 } return slow; //返回慢指针}三.链表中倒数第k个节点1.链接:链表中倒数第k个节点2.题目再现

3.解法 :快慢指针

1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head;

2.因为倒数第k个节点和尾节点的差为 k-1  ,所以我们先让快指针先走 k-1 步;

或者因为尾节点所指向的NULL 和倒数第k个节点相差k,也可以先让快指针走k步;

这个时候慢指针不动;

3.快指针走完后,快指针和慢指针依次走,每次只走1步;

注意,如果是k-1,那么遍历结束的条件是fast->next 是否为空 ,如果是k,那么遍历结束的条件是fast 是否为空;

4.返回慢指针。

演示:

链表倒数第K个节点 快慢指针动态演示

代码:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ){ if(pListHead==NULL) { return NULL; } struct ListNode*slow=pListHead; struct ListNode*fast=pListHead; while(k--) //这里以先走k步为例 { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { slow=slow->next; fast=fast->next; } return slow;}

😽本篇文章到此就结束了,若有错误或是建议,欢迎小伙伴们指出;😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃

本文链接地址:https://www.jiuchutong.com/zhishi/299785.html 转载请保留说明!

上一篇:未来社区的人车房隐私数据权属确认方法(未来社区政策支持)

下一篇:又一个开源第一!飞桨联合百舸,Stable Diffusion推理速度遥遥领先(开源ei)

  • 工商税收是什么意思啊
  • 安防视频监控工程项目
  • 围挡属于什么类型
  • 向个体工商户付款可以现金支付吗
  • 借款当月算利息吗
  • 快递费未支付应该寄走了吗
  • 汽车4s店索赔和维修
  • 对方开票怎么做账务处理
  • 异地预缴增值税后本地怎么申报
  • 无使用价值的存货属于资产吗
  • 以旧换新的会计处理规定
  • 税前计提工资福利费用如何做会计核算?
  • 营改增后房产土地作价入股该如何做税务处理?
  • 进项发票里的印花税如何做账?
  • 企业会计准则规定我国企业的会计期间按年度划分
  • 企业借款增加实际成本
  • 软件行业研发费用比例有要求么
  • 增值税申报错误怎么处理
  • 土地租赁协议和合同有什么区别
  • 企业生产销售白酒取得的下列款项中,应并入
  • 施工项目直接成本和间接成本
  • 没有单据怎么核算成本?
  • win11右下角时间设置
  • 专项储备属于什么科目代码
  • 企业所得税怎么做帐
  • reminder.exe - reminder是什么进程 有什么用
  • php和aspnet哪个好
  • 建筑施工企业关键技术岗位八大员配置要求
  • php数组函数题目
  • 关于增值税专用发票
  • vue 获取当前url
  • php uasort
  • 计提城建税是在当月提吗
  • 一般纳税人在什么情况下,不可以开具增值税专用发票
  • 收到退回的增值税专用发票账务处理
  • 企业会计核算应当以权责发生制为基础
  • vue3定义全局变量
  • php微信公众号获取带参二维码
  • 水果发票税率是几个点
  • 收到的销项负数发票如何申报
  • 无偿调入固定资产怎么入账
  • 差旅费可以抵扣嘛
  • 工程结算是否算成本
  • 收到税控盘退费怎么做分录
  • 企业所得税季度申报表怎么填
  • 营改增后,建筑行业与供应商签合同才怎样签没风险?
  • 持有至到期投资是债权投资吗
  • 租来的办公室装修费摊销几年
  • 新冠肺炎疫情相关租金减让
  • 去年未开票收入未申报
  • 原始凭证的审核要求有哪些
  • sql server设置自增
  • sqlserver2000数据库文件在哪个文件夹
  • Linux/Mac MySQL忘记密码怎么办
  • ubuntu系统升级后无法进入系统
  • centos如何查询版本号
  • 注册表及其作用
  • win7电脑磁盘空间不足清理步骤
  • win7注册表修改开机密码
  • win10预览版和正式版区别
  • win10打
  • windowsxp的主要特点
  • win7关掉wifi
  • win7怎么看磁盘
  • win8能装pr2017吗
  • es6 文档
  • edit apps
  • 我的第一个师父读后感
  • css border-bottom
  • 并结合案例进行深入剖析
  • unity3d,C#使用sqlite作为数据库解决方案思路
  • 批处理 /a
  • python自动化源码
  • 用python编写脚本
  • python 遍历数组
  • 河南省政府非税收网站
  • 交通费用包括
  • 增值税纳税申报表怎么填
  • 贵州省地方税务局历任纪检组长马平
  • 网上交了购置税你要打印出来吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设