Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
** 解题思路 **
用快慢指针，分三步来做。第一步用fast 指针算出链表长度；第二步用slow 指针定位要旋转的位置；第三步作旋转。
Since n may be a large number compared to the length of list. So we need to know the length of linked list.After that, move the list after the (l-k%l )th node to the front to finish the rotation.
Ex: {1,2,3} k=2 Move the list after the 1st node to the front
Ex: {1,2,3} k=5, In this case Move the list after (3-5%3=1)st node to the front.
So the code has three parts.
(1) Get the length
(2) Move to the (l-k%l)th node
(3)Do the rotation
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
int size = 0;
// Get the total length
while (fast.next != null) {
size++;
fast = fast.next;
}
// Get the size - k % size th node
for (int j = size - k % size; j > 0; j--) {
slow = slow.next;
}
// do the rotation
fast.next = dummy.next;
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}
