Given the head of a singly linked list and an integer k, rotate the linked list to the right by k places. The rotation means moving the last k nodes to the front of the list.
Table of Contents
Example:
Input:
Linked List: 1 -> 2 -> 3 -> 4 -> 5
k = 2
Output:
Rotated Linked List: 4 -> 5 -> 1 -> 2 -> 3
Explanation: In the input, the linked list is 1 -> 2 -> 3 -> 4 -> 5, and k = 2. After rotating the list to the right by 2 places, the new linked list becomes 4 -> 5 -> 1 -> 2 -> 3.
Rotate List Solution in C++:
#include <iostream>
// Definition for singly-linked list
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Function to get the length of the linked list
int getLength(ListNode* head) {
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
// Function to rotate the linked list to the right by k places
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr || k == 0) {
return head; // Nothing to rotate
}
int length = getLength(head);
k = k % length; // Reduce k to the range [0, length)
if (k == 0) {
return head; // No rotation needed
}
// Find the new tail and new head of the rotated list
ListNode* oldTail = head;
for (int i = 0; i < length - 1; ++i) {
oldTail = oldTail->next;
}
ListNode* newHead = oldTail->next;
oldTail->next = nullptr; // Break the original loop
// Connect the old head and new head to form the rotated list
ListNode* current = newHead;
while (current->next != nullptr) {
current = current->next;
}
current->next = head;
return newHead;
}
int main() {
// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
int k = 2;
std::cout << "Original Linked List: ";
ListNode* current = head;
while (current != nullptr) {
std::cout << current->val << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
ListNode* rotatedHead = rotateRight(head, k);
std::cout << "Rotated Linked List: ";
current = rotatedHead;
while (current != nullptr) {
std::cout << current->val << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
return 0;
}
Explanation:
- The
rotateRightfunction takes the head of the linked list and an integerkas input and returns the new head of the rotated linked list. - We start by getting the length of the linked list using the
getLengthfunction. - We reduce the value of
kto the range[0, length)by taking the modulo ofkwith the length. This step is necessary because rotating the list by a multiple of the length will result in the same list. - If
kbecomes 0 after the reduction, it means no rotation is needed, and we can return the original head of the list. - To rotate the list to the right by
kplaces, we first find the new tail and the new head of the rotated list. - We break the original loop by setting the
nextpointer of the old tail tonullptr. - We then connect the old head and the new head to form the rotated list.
Time Complexity:
The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The getLength function takes O(n) time to calculate the length of the linked list, and the rest of the operations in the rotateRight function take constant time.
Space Complexity:
The space complexity of this solution is O(1) as we use a constant amount of additional space for variables. The rotation is done in-place without using any additional data structures.