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->nullptr and k = 2, return 4->5->1->2->3->nullptr.

分析

先遍历一遍，得出链表长度len，注意k可能大于len，因此令k %= len。将尾节点next指针指向首节点，形成一个环，接着往后跑len-k步，从这里断开，就是要求的结果了。

代码

  1. // Remove Rotate List
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *rotateRight(ListNode *head, int k) {
  6.         if (head == nullptr || k == 0) return head;
  8.         int len = 1;
  9.         ListNode* p = head;
  10.         while (p->next != nullptr) { // 求长度
  11.             len++;
  12.             p = p->next;
  13.         }
  14.         k = len - k % len;
  16.         p->next = head; // 首尾相连
  17.         for(int step = 0; step < k; step++) {
  18.             p = p->next;  //接着往后跑
  19.         }
  20.         head = p->next; // 新的首节点
  21.         p->next = nullptr; // 断开环
  22.         return head;
  23.     }
  24. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/linked-list/rotate-list.html