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
My Accepted Solution
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
// ListNode* rotateRight(ListNode* head, int k)
ListNode* rotateRight(ListNode* m_head, int count) {
if (!m_head) {
return m_head;
}
int listLength = 0;
auto slowNode = m_head, fastNode = m_head;
while (count > 0) {
--count;
++listLength;
if (fastNode->next) {
fastNode = astNode->next;
} else {
fastNode = m_head;
count %= listLength;
}
}
if (!fastNode) {
return m_head;
}
while (fastNode->next) {
fastNode = fastNode->next;
slowNode = slowNode->next;
}
fastNode->next = m_head;
m_head = slowNode->next;
slowNode->next = nullptr;
return m_head;
}
};