一、题目
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值计算好。
