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.

Solution：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode rotateRight(ListNode head, int n) {

        if(head==null||head.next==null || n==0) return head;

        ListNode fakeHead = new ListNode(0);

        fakeHead.next=head;

        int length=0;

        ListNode start=fakeHead, end=fakeHead;

        for(int i=0; i<n; i++){

            if(end.next==null) break;

            end=end.next;

            length++;

        }

        if(end.next==null){

            //when n>=length

            //int startPos = (length-n)%length+length;      //Or:

            int startPos=n%length;

            if(startPos==0) return fakeHead.next;

            startPos=length-startPos;

            for(int i=0; i<startPos; i++){

                start=start.next;

            }

        }

        else{

            while(end.next!=null){

                start=start.next;

                end=end.next;

            }

        }

        //reorder list

        end.next=fakeHead.next;

        fakeHead.next=start.next;

        start.next=null;

        return fakeHead.next;

    }

}

Note：假设end后移n次后end.next还不是null，说明list的长度>n。则将start和end总体后移。

否则，说明list的长度<=n，这时候须要找到rotate的实际次数。对于一个长为length的list，若rotate的次数为length，则结果为原list。所以rotate的实际次数是n%length，若结果为0，则直接返回原list；否则，须要找到对应的start点，即改动list的起始点。

注意代码中

 int startPos = (length-n)%length+length;      

事实上和

int startPos=n%length;

startPos=length-startPos;

一个效果（startPos不为0时）。可是后者比較好理解。

另外一个负数对一个正数取模，计算例如以下：

result=m%n, where m<=0, n>0

Assume m=xn+result, where x<=0, result<0 and -result<n.

比方(-5)%3。 -5=3*(-1)+(-2)。所以(-5)%3=-2。