当前位置:网站首页>LeetCode_双指针_中等_61. 旋转链表
LeetCode_双指针_中等_61. 旋转链表
2022-07-06 11:32:00 【小城老街】
1.题目
给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
示例 2:
输入:head = [0,1,2], k = 4
输出:[2,0,1]
提示:
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotate-list
2.思路
(1)双指针
详细分析过程见下面代码中的注释。
3.代码实现(Java)
//思路1————双指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//考虑特殊情况
if (k == 0 || head == null || head.next == null) {
return head;
}
//计算链表长度
int length = 0;
ListNode aux = head;
while (aux != null) {
aux = aux.next;
length++;
}
// 当 k > length 时,其旋转结果与 k = k % length 一样
k = k % length;
if (k == 0) {
// k % length 如果等于 0,则说明 length 是 k 的整数倍,旋转之后结果与原来相同,故直接返回 head
return head;
}
/* 设 n = length V1 -> V2 -> ... -> V(n-k-1) -> V(n-k) -> ... -> Vn -> null 将链表每个节点向右移动 k 个位置之后,得到: V(n-k) -> ... -> Vn -> V1 -> V2 -> ... -> V(n-k-1) -> null 所以只需要先找到找到节点 V(n-k-1)、V(n-k) 以及 Vn,然后令 V(n-k-1).next = null Vn.next = V1(即head) 最后返回 V(n-k) 即可 V(n-k-1)、V(n-k) 以及 Vn 分别对应下面代码中的 lastNode、newHead 和最后一个while循环结束后的 aux */
aux = head;
ListNode lastNode = head;
int tmp = length - k;
while (tmp > 0) {
aux = aux.next;
if (tmp != 1) {
lastNode = lastNode.next;
}
tmp--;
}
lastNode.next = null;
ListNode newHead = aux;
while (aux.next != null) {
aux = aux.next;
}
aux.next = head;
return newHead;
}
}
边栏推荐
- Synchronous development of business and application: strategic suggestions for application modernization
- [paper notes] transunet: transformers make strongencoders for medical image segmentation
- [pytorch] yolov5 train your own data set
- LeetCode-1279. 红绿灯路口
- Intelligent supply chain management system solution for hardware and electromechanical industry: digital intelligent supply chain "creates new blood" for traditional industries
- JDBC详解
- 数学知识——高斯消元(初等行变换解方程组)代码实现
- AIRIOT物联网平台赋能集装箱行业构建【焊接工位信息监控系统】
- Abstract classes and abstract methods
- Solution of commercial supply chain management platform for packaging industry: layout smart supply system and digitally integrate the supply chain of packaging industry
猜你喜欢
ROS自定义消息发布订阅示例
思維導圖+源代碼+筆記+項目,字節跳動+京東+360+網易面試題整理
第五期个人能力认证考核通过名单公布
打家劫舍III[后序遍历与回溯+动态规划]
How to type multiple spaces when editing CSDN articles
Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting
Intelligent supply chain management system solution for hardware and electromechanical industry: digital intelligent supply chain "creates new blood" for traditional industries
C language daily practice - day 22: Zero foundation learning dynamic planning
Benefit a lot, Android interview questions
php+redis实现超时取消订单功能
随机推荐
IC设计流程中需要使用到的文件
map的使用(列表的数据赋值到表单,json逗号隔开显示赋值)
Synchronous development of business and application: strategic suggestions for application modernization
Php+redis realizes the function of canceling orders over time
Abstract classes and abstract methods
Precautions for binding shortcut keys of QPushButton
快速幂模板求逆元,逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数
php+redis实现超时取消订单功能
C language daily practice - day 22: Zero foundation learning dynamic planning
Word如何显示修改痕迹
R语言dplyr包进行数据分组聚合统计变换(Aggregating transforms)、计算dataframe数据的分组均值(mean)
PMP practice once a day | don't get lost in the exam -7.6
反射及在运用过程中出现的IllegalAccessException异常
Take a look at how cabloyjs workflow engine implements activiti boundary events
Druid database connection pool details
How word displays modification traces
USB host driver - UVC swap
打家劫舍III[后序遍历与回溯+动态规划]
包装行业商业供应链管理平台解决方案:布局智慧供应体系,数字化整合包装行业供应链
R语言ggplot2可视化:使用ggpubr包的ggstripchart函数可视化分组点状条带图(dot strip plot)、设置add参数为不同水平点状条带图添加箱图