☆打卡算法☆LeetCode 61、旋转链表 算法解析
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个链表的头结点,旋转链表,将链表的每个节点向右移动k个位置。”题目链接:来源:力扣(LeetCode)链接:61. 旋转链...
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个链表的头结点,旋转链表,将链表的每个节点向右移动k个位置。”
题目链接:
来源:力扣(LeetCode)
链接:61. 旋转链表 - 力扣(LeetCode) (leetcode-cn.com)
2、题目描述
给你一个链表的头节点 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]
二、解题
1、思路分析
首先,记录给定链表的长度,注意到当链表向右移动的时候,需要向右移动即可。
将给定的链表连起来,然后将指定位置断开。
之后,计算出链表的长度n,并找到该链表的末尾节点,将其与头结点相连。
将当前闭合为环的链表断开,即可得到答案。
2、代码实现
代码参考:
public class Solution {
public ListNode RotateRight(ListNode head, int k)
{
var length = 0;
var temp = head;
while(temp != null)
{
length ++;
temp = temp.next;
}
if(length == 0 || length == 1)
{
return head;
}
k %= length;
if(k==0)
{
return head;
}
var index = length - k;
var firstNode = head;
var curLastNode = head;
while(index>1)
{
curLastNode = curLastNode.next;
index --;
}
var newHead = curLastNode.next;
curLastNode.next = null;
var nodeTemp = newHead;
//找到后面的链尾 指向之前链表中第一个元素
while(nodeTemp.next != null)
{
nodeTemp = nodeTemp.next;
}
nodeTemp.next = firstNode;
return newHead;
}
}
3、时间复杂度
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
三、总结
链表元素移动和数组形式不同,不需要把每个元素在链上都移动一遍,根据题目我们只要找出要从哪个元素之后开始移动。
一直到链尾都整个指向之前的head元素就行,newHead和前面的链断开,然后这里只要找到newHead后面这条链的链尾指向之前的head即可。
这里还要考虑到K大于链表长度的情况,为了避免无效的计算,应该先把K值计算好。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)