Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109
Solutions
🧠 Cpp
/**
* 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:
//O(n)solution with circular list
ListNode* rotateRight(ListNode* head, int k)
{
if(!head)
return head;
//find list length and save tail
size_t length = 0;
ListNode *tail = nullptr;
for(ListNode *counter = head; counter; ++length, counter = counter->next)
if(!counter->next)
tail = counter;
//make list circular
tail->next = head;
//module k
k = k % length;
//we will move k last element to front
//length - k element will be a new tail
//length - k + 1 element will be a new head
//find new tail:
tail = head;
for(int i = 0; i < length - k - 1; ++i, tail = tail->next);
head = tail->next;
tail->next = nullptr;
return head;
}
};
