【算法萌新闯力扣】:旋转链表

    力扣题目:旋转链表

开篇

  今天是备战蓝桥杯的第25天和算法村开营第3天!经过这3天的学习,感觉自己对链表的掌握程度大大地提升,尤其是在帮村里的同学讨论相关问题时。本篇文章,给大家带来一道旋转链表的题目,用到了巧妙的快慢指针方法!

题目链接: 61.旋转链表

题目描述


在这里插入图片描述

代码思路

 先用双指针策略找到倒数K的位置,也就是{1,2,3}和{4,5}两个序列,之后再将两个链表拼接成{4,5,1,2,3}就行了。具体思路是:
因为k有可能大于链表长度,所以首先获取一下链表长度,如果然后计算应该反转多少次,0次则直接返回原链表。然后
1.快指针先走与反转次数相同的步。
2.慢指针和快指针一起走。
3.快指针走到链表尾部时,慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部,慢指针指向的节点断开和下一节点的联系。
4.返回结束时慢指针指向节点的下一节点。

代码纯享版

class Solution {public ListNode rotateRight(ListNode head, int k) {if(head == null || k == 0) return head;ListNode fast = head, slow = head;int sum = 0;ListNode test = head;while(test != null){sum++;test = test.next;}if(k % sum == 0)return  head;int len = k % sum;while(len > 0){fast = fast.next;len--;}while(fast.next != null){fast = fast.next;slow = slow.next;}ListNode newhead = slow.next;slow.next = null;fast.next = head;return newhead;}
}

代码逐行解析版

class Solution {public ListNode rotateRight(ListNode head, int k) {if(head == null || k == 0) return head; //排除特殊情况,如果不排除,下面的k%sum中会出现sum==0的报错ListNode fast = head, slow = head; //创建快慢指针int sum = 0; ListNode test = head; while(test != null){ //利用test来遍历整个链表sum++; //sum统计链表的长度test = test.next;}if(k % sum == 0)return  head; //k是sum的整数倍,反转完结果与原链表相同,直接返回原链表int len = k % sum; //计算出最终要分开的节点while(len > 0){ //先让快指针领先慢指针len个结点fast = fast.next; len--;}while(fast.next != null){ //两个指针同时移动,当快指针到尾结点时,慢指针到达分开的位置fast = fast.next;slow = slow.next;}ListNode newhead = slow.next; //三步操作,让慢指针后面的部分拼接到头结点slow.next = null;fast.next = head;return newhead; //此时原本慢指针到下一个结点变成头结点,返回它}
}

其他解法

1.第一种是将整个链表反转,如实例1中,把链表变成{5,4,3,2,1},然后再将前K和N-K两个部分分别反转,也就是分别变成了{4,5}和{1,2,3}这样就轻松解决了。

2.力扣官方题解提供了先将链表闭合为环,然后寻找合适的位置断开的解法

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (k == 0 || head == nullptr || head->next == nullptr) {return head;}int n = 1;ListNode* iter = head;while (iter->next != nullptr) {iter = iter->next;n++;}int add = n - k % n;if (add == n) {return head;}iter->next = head;while (add--) {iter = iter->next;}ListNode* ret = iter->next;iter->next = nullptr;return ret;}
};

结语

  如果这道题的分享对您有所帮助,点个关注,为会每天更新力扣题的分享,与大伙儿一同进步!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/206120.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

XC1136 功率传输(PD) Sink控制器IC PD诱骗器芯片 输出可调 可支持多个

XC1136是一款功率传输(PD) Sink控制器IC。XC1136可以从符合Type-CPD协议的电源中请求最大或指定电压。输入电压范围:3V~28V支持USBType-C规范版本1.3支持USB PD2.0和PD3.0通讯协议,最多支持七个电源对象 该XC1136内置拉低电阻CC1和CC2引脚。当XC1136连接到T…

vuepress-----6、时间更新

# 6、时间更新 基于Git提交时间修改文字时间格式 moment # 最后更新时间 # 时间格式修改 下载库文件 yarn add momentconst moment require(moment); moment.locale(zh-cn)module.exports {themeConfig: {lastUpdated: 更新时间,},plugins: [[vuepress/last-updated,{trans…

Vue大屏自适应终极解决方案

v-scale-screenv-scale-screen是一个大屏自适应组件,在实际业务中,我们常用图表来做数据统计,数据展示,数据可视化等比较直观的方式来达到一目了然的数据查看,但在大屏开发过程中,常会因为适配不同屏幕而感…

作为搜索引擎,TikTok超过了谷歌

Rise at Seven通过分析不同行业的数千个关键词进行了研究,突出了用户在TikTok上搜索的100个单词和短语,比在谷歌上搜索的更多。 虽然承认“near me”和“what’s on”的搜索查询仍然是谷歌上最突出的搜索查询,但Rise at Seven得出的结论是&a…

MySQL之redo log

聊聊REDO LOG 为什么需要redolog? 那redolog主要是为了保证数据的持久化,我们知道innodb存储引擎中数据是以页为单位进行存储,每一个页中有很多行记录来存储数据,我们的数据最终是要持久化到硬盘中,那如果我们每进行…

Unity技美35——再URP管线环境下,配置post后期效果插件(post processing)

前两年在我的unity文章第10篇写过,后效滤镜的使用,那时候大部分项目用的还是unity的基础管线,stander管线。 但是现在随着unity的发展,大部分项目都用了URO管线,甚至很多PC端用的都是高效果的HDRP管线,这就…

re:Invent 构建未来:云计算生成式 AI 诞生科技新局面

文章目录 前言一、亚马逊云科技re:Invent二、亚马逊云科技re:Invent 2023 Adam Selipsky 主题演讲三、由亚马逊云科技思想领袖主持的深度探讨四、云计算是什么五、云计算机的主要服务模型六、云计算机的用途七、重构生成式AI 前言 活动介绍 回顾过去十几年,云计算已…

【从浅识到熟知Linux】基本指令之基本权限

🎈归属专栏:从浅学到熟知Linux 🚗个人主页:Jammingpro 🐟每日一句:用博客整理整理之前学过的知识,是个不错的选择。 文章前言:本文介绍Linux中的基本权限及相关指令用法并给出示例和…

基于深度学习的表情动作单元识别综述

论文标题:基于深度学习的表情动作单元识别综述 作者:邵志文1,2,周 勇1,2,谭 鑫3,马利庄3,4,刘 兵1,2,姚 睿1,2 发表日期&#xff1a…

MxL3706-AQ-R 2.0通道绑定同轴网络集成电路特性

MxL3706-AQ-R是Max线性公司的第三代MoCA2.0同轴网络控Z器SoC,可用于在现有的家庭同轴电缆上创建具有千兆位吞吐量性能的家庭网络。 该MxL3706-AQ-R工作在400MHz至1675MHz之间的无线电频率,并与satellite共存,电X和有线电视运营商的频率计划。…

毕业设计单片机可以用万能板吗?

毕业设计单片机可以用万能板吗? 可以是可以,就是焊接起来比较麻烦,特别是有好几个重复连线点的时候,检测起来就不那么容易了,而且布线看起来乱糟糟的,如果后期一不小心把线弄断了,查起来就更麻烦了&#x…

机器人与3D视觉 Robotics Toolbox Python 一 安装 Robotics Toolbox Python

一 安装python 库 前置条件需要 Python > 3.6,使用pip 安装 pip install roboticstoolbox-python测试安装是否成功 import roboticstoolbox as rtb print(rtb.__version__)输出结果 二 Robotics Toolbox Python样例程序 加载机器人模型 加载由URDF文件定义…

element ui 表格合计项合并

如图所示&#xff1a; 代码&#xff1a; <el-table height"400px" :data"tableData " borderstyle"width: 100%"stripe show-summaryref"table"id"table"> </el-table>监听表格 watch: { //监听table这个对象…

Rational Arithmetic

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 ☁️有理数运算 实现对两个有理数的…

【JavaEE初阶】volatile 关键字、wait 和 notify

目录 一、volatile 关键字 1、volatile 能保证内存可见性 2、volatile 不保证原子性 二、wait 和 notify 1、wait()方法 2、notify()方法 3、notifyAll()方法 4、wait 和 sleep 的对比 一、volatile 关键字 1、volatile 能保证内存可见性 我们前面的线程安全文章中&…

VGN S99快捷键,说明书

VGN S99快捷键-说明书 按键说明灯光效果常见疑难 按键说明 切换关闭电量指示灯&#xff1a;Fn home 灯光效果 常见疑难

【JavaEE】线程安全与线程状态

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文于《JavaEE》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&…

利用 LD_PRELOAD劫持动态链接库,绕过 disable_function

目录 LD_PRELOAD 简介 程序的链接 动态链接库的搜索路径搜索的先后顺序&#xff1a; 利用LD_PRELOAD 简单的劫持 执行id命令 反弹shell 引申至 PHP 绕过disable_function 方法1&#xff1a;使用蚁剑的扩展工具绕过disable_function 方法2&#xff1a;利用 mail 函数…

时序预测 | Python实现TCN时间卷积神经网络价格预测

时序预测 | Python实现TCN时间卷积神经网络时间序列预测 目录 时序预测 | Python实现TCN时间卷积神经网络时间序列预测预测效果基本介绍模型描述程序设计参考资料预测效果 基本介绍 时间卷积网络,TCN。 利用CNN技术处理时间序列数据。 卷基础层有三种,第一种是一维CNN,用于输…

Chrome显示分享按钮

分享按钮不见了&#xff01; Chrome://flags Chrome Refresh 2023 Disabled 左上角的标签搜索会到右上角。