61. 旋转链表
问题
给定一个链表，旋转链表，将链表每个节点向右移动 个位置，其中
是非负数。
示例 1:
输入:
输出:
解释:
向右旋转 1 步:
向右旋转 2 步:
示例 2:
输入:
输出:
解释:
向右旋转 1 步:
向右旋转 2 步:
向右旋转 3 步:
向右旋转 4 步:
解法1
一开始可以发现，有如下三种特殊情况是可以直接不进行任何处理，直接返回head的：
-
为
，整个链表都是
-
为空，代表链表只有一个元素，此时不论右移多少次，都是本身
考虑的取值, 如果
的值正好是链表长度的整数倍，这种情况右移后还是原链表本身。返回即可。
接下来，如果远远超过链表的长度，我们也没必要进行过多的右移，获取
对链表长度的余数即为右移的次数。
一个难点在于，在单向链表中找到一个元素的父亲节点的时间复杂度很高。此时第一个想法是翻转链表、新链表左移、再次翻转链表。
也写出了第一版代码。
代码1
java实现
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//三种情况，链表为空、链表只有一个元素、移动位置为0
if (head == null ||head.next == null || k == 0) {
return head;
}
ListNode tail = head;
ListNode temp = head;
//判断长度
int i = 1;
while (temp.next != null) {
temp = temp.next;
i++;
}
k = k % i;
//当旋转整数倍时，没有必要挪动数据，直接返回head
if (k == 0) {
return head;
}
//翻转链表
head = reverse(head);
while(k>0) {
tail.next = head;
tail = head;
head = head.next;
tail.next = null;
k--;
}
head = reverse(head);
return head;
}
//翻转链表
ListNode reverse (ListNode head) {
ListNode prev = head;
ListNode curr = head.next;
while (curr!=null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head.next = null;
return prev;
}
}
解法2
解法1的问题在于有两次翻转链表，虽然只是的时间复杂度，但是本着能少一步是一步的原则，还是能省则省。
继续观察示例1，发现，右移位，实际上是左移
位，而左移是解法1里就实现了的。这就不需要翻转链表就可以直接移动了。
代码2
java实现
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//三种情况，链表为空、链表只有一个元素、移动位置为0
if (head == null ||head.next == null || k == 0) {
return head;
}
ListNode tail = head;
ListNode temp = head;
//判断长度
int i = 1;
while (tail.next != null) {
temp = tail;
tail = tail.next;
i++;
}
k = k % i;
//当旋转整数倍时，没有必要挪动数据，直接返回head
if (k == 0) {
return head;
}
//增加了一步k的计算
k = i-k;
//翻转链表
//注释掉解法1的翻转链表
//head = reverse(head);
while(k>0) {
tail.next = head;
tail = head;
head = head.next;
tail.next = null;
k--;
}
//注释掉解法1的翻转链表
//head = reverse(head);
return head;
}
//翻转链表
ListNode reverse (ListNode head) {
ListNode prev = head;
ListNode curr = head.next;
while (curr!=null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head.next = null;
return prev;
}
}
仔细观察代码，实际上是去掉了翻转链表，对k进行了更进一步的操作而已。相比解法一，代码更加的清晰。
