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.

这题要求把链表后面k个节点轮转到链表前面。

对于这题我们首先需要遍历链表，得到链表长度n，因为k可能大于n，所以我们需要取余处理，然后将链表串起来形成一个换，在遍历n - k % n个节点，断开，就成了。譬如上面这个例子，k等于2，我们遍历到链表结尾之后，连接1，然后遍历 5 - 2 % 5个字节，断开环，下一个节点就是新的链表头了。

代码如下：

  1. class Solution {
  2. public:
  3.     ListNode *rotateRight(ListNode *head, int k) {
  4.         if(!head || k == 0) {
  5.             return head;
  6.         }
  8.         int n = 1;
  9.         ListNode* p = head;
  10.         //得到链表长度
  11.         while(p->next) {
  12.             p = p->next;
  13.             n++;
  14.         }
  16.         k = n - k % n;
  18.         //连接成环
  19.         p->next = head;
  21.         for(int i = 0; i < k; i++) {
  22.             p = p->next;
  23.         }
  25.         //得到新的链表头并断开环
  26.         head = p->next;
  27.         p->next = NULL;
  28.         return head;
  29.     }
  30. };