当前位置:网站首页>LeetCode_ Double pointer_ Medium_ 61. rotating linked list
LeetCode_ Double pointer_ Medium_ 61. rotating linked list
2022-07-06 19:29:00 【Old street of small town】
1. subject
Give you a list of the head node head , Rotate the list , Move each node of the list to the right k A place .
Example 1:
Input :head = [1,2,3,4,5], k = 2
Output :[4,5,1,2,3]
Example 2:
Input :head = [0,1,2], k = 4
Output :[2,0,1]
Tips :
The number of nodes in the linked list is in the range [0, 500] Inside
-100 <= Node.val <= 100
0 <= k <= 2 * 109
source : Power button (LeetCode)
link :https://leetcode.cn/problems/rotate-list
2. Ideas
(1) Double pointer
See the comments in the following code for the detailed analysis process .
3. Code implementation (Java)
// Ideas 1———— Double pointer
/** * 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) {
// Consider special circumstances
if (k == 0 || head == null || head.next == null) {
return head;
}
// Calculate the length of the list
int length = 0;
ListNode aux = head;
while (aux != null) {
aux = aux.next;
length++;
}
// When k > length when , Its rotation results are consistent with k = k % length equally
k = k % length;
if (k == 0) {
// k % length If it is equal to 0, shows length yes k Integer multiple , After the rotation, the result is the same as the original , So go straight back to head
return head;
}
/* set up n = length V1 -> V2 -> ... -> V(n-k-1) -> V(n-k) -> ... -> Vn -> null Move each node of the list to the right k After two positions , obtain : V(n-k) -> ... -> Vn -> V1 -> V2 -> ... -> V(n-k-1) -> null So you just need to find the node first V(n-k-1)、V(n-k) as well as Vn, Then make V(n-k-1).next = null Vn.next = V1( namely head) Finally back to V(n-k) that will do V(n-k-1)、V(n-k) as well as Vn Corresponding to lastNode、newHead And the last while At the end of the cycle 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;
}
}
边栏推荐
- spark基础-scala
- C language daily practice - day 22: Zero foundation learning dynamic planning
- Computer network: sorting out common network interview questions (I)
- Application of clock wheel in RPC
- 如何自定义动漫头像?这6个免费精品在线卡通头像生成器,看一眼就怦然心动!
- 全套教学资料,阿里快手拼多多等7家大厂Android面试真题
- CCNP Part 11 BGP (III) (essence)
- Simple understanding of MySQL database
- Lucun smart sprint technology innovation board: annual revenue of 400million, proposed to raise 700million
- 冒烟测试怎么做
猜你喜欢
史上超级详细,想找工作的你还不看这份资料就晚了
Spark foundation -scala
今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
学习探索-无缝轮播图
【翻译】Linkerd在欧洲和北美的采用率超过了Istio,2021年增长118%。
Mathematical knowledge -- code implementation of Gaussian elimination (elementary line transformation to solve equations)
Black Horse - - Redis Chapter
Solution of commercial supply chain management platform for packaging industry: layout smart supply system and digitally integrate the supply chain of packaging industry
Mysql Information Schema 学习(二)--Innodb表
Word如何显示修改痕迹
随机推荐
Lick the dog until the last one has nothing (simple DP)
Documents to be used in IC design process
冒烟测试怎么做
DaGAN论文解读
接雨水问题解析
C # - realize serialization with Marshall class
学习探索-无缝轮播图
C # use Marshall to manually create unmanaged memory in the heap and use
Simple understanding of MySQL database
五金机电行业智能供应链管理系统解决方案:数智化供应链为传统产业“造新血”
Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
Actf 2022 came to a successful conclusion, and 0ops team won the second consecutive championship!!
Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
The second day of rhcsa study
Mind map + source code + Notes + project, ByteDance + JD +360+ Netease interview question sorting
Pytorch common loss function
R language ggplot2 visualization: use ggviolin function of ggpubr package to visualize violin diagram
业务与应用同步发展:应用现代化的策略建议
Mathematical knowledge -- code implementation of Gaussian elimination (elementary line transformation to solve equations)
In depth analysis, Android interview real problem analysis is popular all over the network