题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：闭合为环
思路：
代码示例：（Java）
@Data
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public class Solution1 {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
while (iter.next != null) {
iter = iter.next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
iter.next = head;
while (add-- > 0) {
iter = iter.next;
}
ListNode ret = iter.next;
iter.next = null;
return ret;
}
}
复杂度分析
- 时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。
- 空间复杂度：O(1)，我们只需要常数的空间存储若干变量。
