Задача с собеседования в Amazon

Дан указатель на первый элемент связного списка. Нужно циклически сдвинуть список на k позиций.
Структура связного списка определяется следующим образом:
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) {}
};

Пример:
Список [1, 2, 3, 4, 5], k = 2
Вывод: [4, 5, 1, 2, 3]

0 <= N <= 500 - количество элементов в списке
0 <= k <= 2*10^9

Решение:
В первую очередь заметим, что k может быть очень большим, поэтому, очевидно, что можем сделать k %= N.

Идея очень простая: каждый раз будем брать последний элемент в списке, пометим для него следующим головной, а для предыдущего next сделаем пустым. Для удобного поддержания последнего в сдвиге элемента будем использовать дек, в который пушаем в начало текущую голову.

Также незабываем обработать крайние случаи
1) Пустой список
2) Список, состоящий из 1 элемента

ListNode* rotateRight(ListNode* head, int k) {
if (!head)
return nullptr;

deque<ListNode*> d;
d.push_back(head);

ListNode* cur = head->next;
while (cur) {
d.push_back(cur);
cur = cur->next;
}

if (d.size() == 1)
return head;

k %= (int)d.size();

while (k--) {
ListNode* last = d.back();
d.pop_back();
ListNode* predlast = d.back();

predlast->next = nullptr;
last->next = head;
d.push_front(last);
head = last;
}

return head;
}

Решение за O(N)

@algoses