61. Rotate List
1. Description
Given the head of a linked list, rotate the list to the right by k places.
2. Example
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]
3. Constraints
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10$^{9}$
4. Solutions
Two Pointers
n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
int length = 0;
ListNode *last = nullptr;
for (auto iter = head; iter != nullptr; iter = iter->next) {
++length;
last = iter;
}
if (length == 0 || k % length == 0) {
return head;
}
k %= length;
ListNode *iter = head, *prev_pivot = head;
for (int i = 0; i < k; ++i) {
iter = iter->next;
}
while (iter->next != nullptr) {
iter = iter->next;
prev_pivot = prev_pivot->next;
}
ListNode *rotated_head = prev_pivot->next;
prev_pivot->next = nullptr;
last->next = head;
return rotated_head;
}
};