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.

注意一些边界的处理，找到n-k+1个节点后处理移位。

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     int calListLen(ListNode *node)12     {13         int len = 0;14         while(node)15         {16             len++;17             node = node->next;18         }19         return len;20     }21     22     ListNode *rotateRight(ListNode *head, int k) {23         // Start typing your C/C++ solution below24         // DO NOT write int main() function25         if (head == NULL)26             return NULL;27             28         int len = calListLen(head);29         30         k = k % len;31         32         if (k == 0)33             return head;34         35         ListNode *p = head;36         ListNode *pPre = NULL;37         38         for(int i = 0; i < len - k; i++)39         {40             pPre = p;41             p = p->next;42         }43         44         ListNode *q = p;45         while(q->next)46             q = q->next;47             48         if (pPre)49             pPre->next = NULL;50             51         q->next = head;52         53         return p;        54     }55 };