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.

 

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* rotateRight(ListNode* head, int k) {12         if(head==NULL||head->next==NULL||k==0)13             return head;14         ListNode* bf=head;15         ListNode* newhead=head,*end=head;16         int length=1;17         while(end->next!=NULL){18             end=end->next;19             length++;20         }21         end=head;22         if(k>length){23             k=k%length;24         }25         if(k==length||k==0)26             return head;27         k--;28         while(k>0&&end->next!=NULL){29             end=end->next;30             k--;31         }32         while(end->next!=NULL){33             end=end->next;34             bf=newhead;35             newhead=newhead->next;36         }37 38         bf->next=NULL;39         end->next=head;40         return newhead;41 42     }43 };