# 61. Rotate List
Difficulty: Medium

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-11-14
**/
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;

#if defined(_MSC_VER) && defined(_DEBUG)
  #define _CRTDBG_MAP_ALLOC
  #include <crtdbg.h>
#endif // end of if defined(_MSC_VER) && defined(_DEBUG)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
 public:
  static ListNode *rotateRight(ListNode *head, int k) {
    if (head == nullptr) {
      return nullptr;
    }

    vector<ListNode *> node_vec;
    while (head != nullptr) {
      node_vec.emplace_back(head);
      head = head->next;
    }
    const auto kNodeCount = node_vec.size();
    if (kNodeCount == 1) {
      return *(node_vec.begin());
    }

    (*node_vec.rbegin())->next = *(node_vec.begin());

    auto rotate_steps = k % kNodeCount;
    auto head_index = (rotate_steps > 0) ? kNodeCount - rotate_steps : 0;
    auto tail_index = (head_index > 0) ? head_index - 1 : kNodeCount - 1;

    head = node_vec[head_index];
    node_vec[tail_index]->next = nullptr;

    return head;
  }
};

template<typename InputIterator, typename InputSentinel, typename Node>
void createLinkedList(InputIterator first,
                      InputSentinel last, Node *&head);

template<typename Node>
void printLinkedList(Node *head);

template<typename Node>
void releaseLinkedList(Node *&head);

int main(int argc, char *argv[]) {
  vector<int> nums = {1, 2, 3, 4, 5};
  ListNode *head = nullptr;
  createLinkedList(nums.begin(), nums.end(), head);
  printLinkedList(head);
  releaseLinkedList(head);

#if defined(_MSC_VER) && defined(_DEBUG)
  _CrtDumpMemoryLeaks();
#endif
  return EXIT_SUCCESS;
}

template <typename InputIterator, typename InputSentinel, typename Node>
void createLinkedList(InputIterator first,
                      InputSentinel last, Node *&head) {
  head = (first != last)? new Node(*first++) : nullptr;
  Node *temp = head;
  while (first != last) {
    temp->next = new Node(*first++);
    temp = temp->next;
  }
}

template <typename Node>
void printLinkedList(Node *head) {
  while (head != nullptr) {
    cout << head->val << " -> ";
    head = head->next;
  }
  cout << "(nullptr)" << endl;
}

template <typename Node>
void releaseLinkedList(Node *&head) {
  while (head != nullptr) {
    auto *temp = head;
    head = head->next;
    delete temp;
  }
}

## Result
Success
Details
Runtime: 8 ms, faster than 86.45% of C++ online submissions for Rotate List.
Memory Usage: 12.4 MB, less than 6.13% of C++ online submissions for Rotate List.

###### tags: `LeetCode-Medium` `C++` `C++_template`