Question:
http://leetcode.com/2010/04/rotating-array-in-place.html
Rotate a one-dimensional array of n elements to the right by k steps.
For instance, with n=7 and k=3, the array {a, b, c, d, e, f, g} is rotated to {e, f, g, a, b, c, d}
// O (n)
public void rotate(int[] A, int k)
{
// Assumptions:
// A not null
// A not empty
// if k > 0, rotate >>,
// if k < 0, rotate <<.
//
// rotatedIndex = ( originalIndex + k ) % len
int len = A.length;
int original = 0;
int from = A[0];
do
{
// Calculate rotated index
int rotated = (original + k) % len;
// Assign expected value to rotated.
int temp = A[rotated];
A[rotated] = from;
// Save expected index for next rotated value.
from = temp;
original = rotated;
}
while (original != 0);
}What if Rotate a list?
http://7371901.blog.51cto.com/7361901/1598840
// O (n)
public ListNode rotate(ListNode head, int k)
{
if (head == null || head.next == null || k == 0)
return head; // No need further
int size = 1;
ListNode tail = head;
while (tail.next != null)
{
tail = tail.next;
size ++;
}
// Re-calculate k in case k is negative.
k = ((k % size) + size) % size;
int newTailIndex = size - 1 - k;
ListNode newTail = head;
for (int i = 0 ; i < newTailIndex ; i ++)
{
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
tail.next = head;
return newHead;
}[LeetCode] Rotate Array / List
原文：http://7371901.blog.51cto.com/7361901/1605235