61. 旋转链表 medium + 使用列队旋转列表

总体思路：

1. 把所有的链表节点放入队列中，右旋k次，其实就是左旋q.size() - k次, 然后创建链表输出

2. 注意：如果右旋超过节点数量，等于仅仅右旋了k%q.size()次，举例：5节点右旋5次，等于没变。

3. 优化点：建议放弃queue和stack，分别使用deque和vector去代替这两种容器适配器，毕竟掌握队列和栈的应用和思想更重要。这两种容器适配器无法遍历。无法直接打印里面的数据。

/**
 * 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) {}
 * };
 */

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // always considering the input parameters
        if (head == nullptr) {
            return head;
        }

        // 将所有节点放入队列
        queue<int> q;
        ListNode* cur = head;
        while (cur != nullptr) {
            q.push(cur->val);
            cur = cur->next;
        }

        // 左旋几次，因为使用了queue适配器，不太好右旋
        int size = q.size();
        for (int i = 1; i <= (size - k%size); i++) {
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }

        // 创建首节点
        ListNode* newHead = new ListNode(q.front());
        ListNode* traversal = newHead;
        q.pop();
        // 对之后的节点进行依次添加；
        size = q.size();
        while (size--) {
            ListNode* tmp = new ListNode(q.front());
            q.pop();
            traversal ->next = tmp;
            traversal = traversal->next;
        }

        return newHead;
    }
};