61. 旋转链表

问题

给定一个链表，旋转链表，将链表每个节点向右移动 k个位置，其中 k是非负数。

示例 1:

输入: 1?>2?>3?>4?>5?>NULL,k=2

输出: 4?>5?>1?>2?>3?>NULL

解释:

向右旋转 1 步: 5?>1?>2?>3?>4?>NULL

向右旋转 2 步: 4?>5?>1?>2?>3?>NULL

示例 2:

输入: 0?>1?>2?>NULL,k=4

输出: 2?>0?>1?>NULL

解释:

向右旋转 1 步: 2?>0?>1?>NULL

向右旋转 2 步: 1?>2?>0?>NULL

向右旋转 3 步: 0?>1?>2?>NULL

向右旋转 4 步: 2?>0?>1?>NULL

解法1

一开始可以发现，有如下三种特殊情况是可以直接不进行任何处理，直接返回head的：

• head为null，整个链表都是null
• head的next为空，代表链表只有一个元素，此时不论右移多少次，都是本身
• k=0

考虑k的取值, 如果k的值正好是链表长度的整数倍，这种情况右移后还是原链表本身。返回即可。

接下来，如果k远远超过链表的长度，我们也没必要进行过多的右移，获取k对链表长度的余数即为右移的次数。

一个难点在于，在单向链表中找到一个元素的父亲节点的时间复杂度很高。此时第一个想法是翻转链表、新链表左移、再次翻转链表。

也写出了第一版代码。

代码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的问题在于有两次翻转链表，虽然只是O(n)

的时间复杂度，但是本着能少一步是一步的原则，还是能省则省。

继续观察示例1，发现，右移2

位，实际上是左移3

位，而左移是解法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进行了更进一步的操作而已。相比解法一，代码更加的清晰。