Rotate List

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.

Follow the same idea as find the kth rightmost node in the list, then move that pointer until the last element in the linked list.

for k=2, after move

1->2->3(last)->4->5(current)

last.next will be the new head

Corner case: we need to find the length of the linkedlist to avoid the case k is larger then the length of the linkedlist.

public ListNode rotateRight(ListNode head, int n) {
         if (head==null||head.next==null) {
             return head;
         }

         //find the length of the list 
         ListNode current = head;
         int length = 0;
         while (current!=null) {
             length = length+1;
             current = current.next;
         }

         //calculate the number of rotation times
         n = n % length;
         if (n==0) {
             return head;
         }

         //move to the nth to rightmost node
         current = head;
         while(n>0 && current!=null) {
             current = current.next;
             n--;
         }

         //after this, last will be the new last node
         ListNode last = head;
         while(current.next!=null) {
             last = last.next;
             current = current.next;
         }

         /*
          * n = 2
          * original 1->2->3->4->5 after move,
          * current = oldEnd = 5, last = newEnd = 3
          * 
          */

         ListNode newHead = last.next;
         last.next = null;
         current.next = head;

         return newHead;
    }