# 【LeetCode】 61. Rotate List

## Description
> Given a linked list, rotate the list to the right by k places, where k is non-negative.

> 給一個linked list，請將它往右旋轉k次，k為一非負數。

## Example:

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL


Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

## Solution

* 先做出往右一次，用for跑k次。
* 當list大小只有n的時候，轉n次就會回到原狀，所以可以將k%n加速。
* 如果list只有兩個元素的時候要做一些修正。
* 我感覺可以一次到位，這個作法應該是算偏慢，有時間再回來想。

### Code

class Solution {
public:
  ListNode* RightTurn(ListNode* head)
  {
      //only two
      if (head->next->next == NULL)
      {
          head->next->next = head;
          head = head->next;
          head->next->next = NULL;
          return head;
      }
      ListNode* last = head;
      while (last->next->next)
          last = last->next;
      last->next->next = head;
      head = last->next;
      last->next = NULL;
      return head;
  }
  ListNode* rotateRight(ListNode* head, int k) {
      int s = 0;
      for (ListNode*temp = head; temp; s++)
          temp = temp->next;
      if(s==0 || s==1) return head;
      k %= s;

      for (int i = 0; i < k; i++)
          head = RightTurn(head);
      return head;
  }
};

###### tags: `LeetCode` `C++`