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) {
if (head == nullptr || k == 0) {
return head;
}
int move_step = 0;
ListNode *fast = head;
while (move_step < k && fast->next != nullptr) {
fast = fast->next;
++move_step;
}
if (move_step == k) {
ListNode *slow = head;
while (fast->next != nullptr) {
slow = slow->next;
fast = fast->next;
}
ListNode *new_head = slow->next;
slow->next = nullptr;
fast->next = head;
return new_head;
} else {
return rotateRight(head, k % (move_step + 1));
}
}
};