Leetcode61 旋转链表 中等
程序员文章站
2022-06-18 19:41:39
题目:思路:仔细思考后旋转链表其实就相当于链表有个环,旋转后改变了头结点而已。接下来可以找到一个关系,以题目示例1为例假设5的next-1,也就是有一个环,那么移动后的头结点有什么规律移动1,新头结点=倒数第一个=正数第5个移动2,新头结点=倒数第二个=正数第4个移动3,新头结点=倒数第三个=正数第3个移动4,新头结点=倒数第四个=正数第2个移动5=没移动可以发现,新头结点=原链表正数第(链表长-移动步数+1)个那么只需要头结点正向移动(链表长-移动步数)个就能到达新头结点总结:...
题目:
思路:
仔细思考后旋转链表其实就相当于链表有个环,旋转后改变了头结点而已。
接下来可以找到一个关系,以题目示例1为例
假设5的next-1,也就是有一个环,那么移动后的头结点有什么规律
移动1,新头结点=倒数第一个=正数第5个
移动2,新头结点=倒数第二个=正数第4个
移动3,新头结点=倒数第三个=正数第3个
移动4,新头结点=倒数第四个=正数第2个
移动5=没移动
可以发现,新头结点=原链表正数第(链表长-移动步数+1)个
那么只需要头结点正向移动(链表长-移动步数)个就能到达新头结点
总结:
- 先修改链表成环
- 计算新头结点=正向移动多少步
- 把环撤销
代码:
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null){
return null;
}
int len = 1;
//pHead是辅助指针,接下来进行重复使用,不再新建额外ListNode对象
ListNode pHead = head;
//计算链表长
while(pHead.next != null){
len++;
pHead = pHead.next;
}
//计算要移动多少步,对链表长求余即可,避免不必要的移动,减少移动次数
int move = k % len;
if(move == 0){
return head;
}
//修改链表成环
pHead.next = head;
ListNode newHead;
pHead = head;
int moveCount = len-(move-1)-1;
//找新头结点
while(moveCount > 0){
pHead = pHead.next;
moveCount--;
}
newHead = pHead;
len--;
//移动len-1步到达末尾,把环去掉
while(len > 0){
pHead = pHead.next;
len--;
}
pHead.next = null;
return newHead;
}
}
本文地址:https://blog.csdn.net/weixin_40208575/article/details/107878889