“给定一个链表的头结点,旋转链表,将链表的每个节点向右移动k个位置。”
题目链接:
来源:力扣(LeetCode)
链接:61. 旋转链表 - 力扣(LeetCode) (leetcode-cn.com)
给你一个链表的头节点 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]
首先,记录给定链表的长度,注意到当链表向右移动的时候,需要向右移动即可。
将给定的链表连起来,然后将指定位置断开。
之后,计算出链表的长度n,并找到该链表的末尾节点,将其与头结点相连。
将当前闭合为环的链表断开,即可得到答案。
代码参考:
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;
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
链表元素移动和数组形式不同,不需要把每个元素在链上都移动一遍,根据题目我们只要找出要从哪个元素之后开始移动。
一直到链尾都整个指向之前的head元素就行,newHead和前面的链断开,然后这里只要找到newHead后面这条链的链尾指向之前的head即可。
这里还要考虑到K大于链表长度的情况,为了避免无效的计算,应该先把K值计算好。