Rotate a Linked List to the Right by K Places

102.2k
0

Given the head of a singly linked list and an integer k, rotate the linked list to the right by k places.

In a right rotation, the last node becomes the first node, and every remaining node moves one position toward the right. Return the head of the rotated linked list.

Example 1

Input: head = [1, 2, 3, 4, 5], k = 2

Output: [4, 5, 1, 2, 3]

Explanation: After one right rotation, list becomes [5, 1, 2, 3, 4]. After two right rotations, list becomes [4, 5, 1, 2, 3].

Example 2

Input: head = [0, 1, 2], k = 4

Output: [2, 0, 1]

Explanation: List length equals 3, so 4 % 3 = 1 effective right rotation gives [2, 0, 1].

Brute Force Approach

A right rotation can be performed by moving the last node of the linked list to the front. Since one such operation rotates the list by one position, repeating it k times gives the required result.

Before performing rotations, we first count the length of the linked list and reduce k using k % length. This avoids unnecessary full-cycle rotations because rotating a list by its length brings it back to the same order.

For every effective rotation, we traverse the list until the second last node, detach the last node, place it before the current head, and update the head pointer.

Algorithm

  • Return head directly when the list is empty, has only one node, or k = 0, as none of these cases can produce a different ordering.

  • Count the total number of nodes in the linked list, since the effective number of rotations depends on the list length.

  • Reduce the rotations using k = k % length, as rotating the list by its full length brings it back to the original order.

  • Repeat the rotation process k times, with each iteration moving the last node to the front and therefore producing one right rotation.

  • For each rotation, traverse the list until the second-last node, as this node is needed to detach the last node from the list.

  • Store the last node, set the second-last node's next to NULL, and link the last node to the current head, since placing the last node before the head creates one right rotation.

  • Update head to the moved last node, as it now becomes the first node of the rotated list.

  • Return the updated head after all effective rotations have been completed.

Dry Run

rotate list brute force

rotate list brute force

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
Node* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
/* Rotates the linked list to the right by k places */
ListNode* rotateRight(ListNode* head, int k) {
// Handle empty list, single node, or zero rotations
if (head == nullptr || head->next == nullptr || k == 0) {
return head;
}
int length = 0;
ListNode* temp = head;
// Calculate total length of the list
while (temp != nullptr) {
length++;
temp = temp->next;
}
// Remove redundant full cycles
k = k % length;
// Rotate the list one node at a time
while (k > 0) {
ListNode* secondLast = nullptr;
ListNode* last = head;
// Traverse to the end of the list
while (last->next != nullptr) {
secondLast = last;
last = last->next;
}
// Move the last node to the front
secondLast->next = nullptr;
last->next = head;
head = last;
k--;
}
return head;
}
};
ListNode* buildList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
ListNode* head = new ListNode(values[0]);
ListNode* current = head;
for (int i = 1; i < (int)values.size(); i++) {
current->next = new ListNode(values[i]);
current = current->next;
}
return head;
}
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) {
cout << " -> ";
}
current = current->next;
}
cout << endl;
}
/* Driver code entry point */
int main() {
vector<int> values = {1, 2, 3, 4, 5};
int k = 2;
ListNode* head = buildList(values);
Solution solution;
ListNode* answer = solution.rotateRight(head, k);
printList(answer);
return 0;
}

Complexity Analysis

Time Complexity: O(n + (k % n) × n), The list is traversed once to find its length, and each effective rotation takes O(n) time to find the last node. In the worst case, this becomes O(n²).

Space Complexity: O(1), The list is rotated in-place using only a few pointer variables, so no extra space proportional to the list size is required.

Optimal Approach

Instead of rotating the linked list one step at a time, we first connect the tail node to the head node and temporarily convert the list into a circular linked list. This keeps all nodes connected in order and allows us to choose the correct breaking point directly.

For a right rotation by k, the actual number of rotations is k % length. The new head will be at position length - k from the beginning, and the node just before it becomes the new tail. After locating the new tail, we break the circular link and return the new head.

Algorithm

  • Return head directly when the list is empty, has only one node, or k = 0, as none of these cases changes the list's order.

  • Traverse the list once to count its length and locate the tail node, since both the effective rotations and the point where the list should be split depend on the length.

  • Reduce the rotations using k = k % length, as rotating by the full length restores the original order; if k = 0, the original head is already the required result.

  • Connect the tail node to the head, temporarily forming a circular linked list, which keeps the entire sequence connected while the new starting point is located.

  • Move length - k - 1 steps from the original head to reach the node that should become the new tail, since the node immediately after it will become the new head.

  • Set newHead = newTail->next, as this node is exactly the position where the rotated list should begin.

  • Break the circular link by setting newTail->next = NULL, which restores the list as a normal singly linked list.

  • Return newHead as the head of the right-rotated linked list.

Dry Run

rotate list optimal

rotate list optimal

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
Node* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Rotates the linked list by k places using a circular connection
ListNode* rotateRight(ListNode* head, int k) {
// Handle empty list, single node, or zero rotations
if (head == nullptr || head->next == nullptr || k == 0) {
return head;
}
int length = 1;
ListNode* tail = head;
// Locate the tail node while calculating list length
while (tail->next != nullptr) {
tail = tail->next;
length++;
}
// Skip redundant complete rotation cycles
k = k % length;
if (k == 0) {
return head;
}
// Link tail to head to form a temporary circle
tail->next = head;
int stepsToNewTail = length - k - 1;
ListNode* newTail = head;
// Traverse to locate the node that will serve as the new tail
for (int step = 0; step < stepsToNewTail; step++) {
newTail = newTail->next;
}
// Pinpoint the new head node next to the new tail
ListNode* newHead = newTail->next;
// Break the circular reference to restore linear list structure
newTail->next = nullptr;
return newHead;
}
};
ListNode* buildList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
ListNode* head = new ListNode(values[0]);
ListNode* current = head;
for (int i = 1; i < (int)values.size(); i++) {
current->next = new ListNode(values[i]);
current = current->next;
}
return head;
}
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) {
cout << " -> ";
}
current = current->next;
}
cout << endl;
}
/* Driver code entry point */
int main() {
vector<int> values = {1, 2, 3, 4, 5};
int k = 2;
ListNode* head = buildList(values);
Solution solution;
ListNode* answer = solution.rotateRight(head, k);
printList(answer);
return 0;
}

Complexity Analysis

Time Complexity: O(n), one traversal counts length and another partial traversal locates the break point.

Space Complexity: O(1), only pointer variables are used.

FAQs

Q1. Why do we calculate k % length before rotating the linked list?
Rotating a linked list by its length brings it back to the original order. Therefore, only the remaining rotations after complete cycles need to be performed.

Q2. How is the new head found in the optimal approach?
After reducing k, the new head is the node at position length - k from the beginning of the list. The node just before it becomes the new tail.

Q3. Why is the linked list converted into a circular linked list?
Making the list circular avoids repeatedly moving nodes. After locating the new tail, the circular link is broken to obtain the rotated linked list.

Q4. What happens if k % length is equal to 0?
It means the rotations complete one or more full cycles, so the linked list remains unchanged and the original head is returned.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links inste...

59.9k
Linked List

Sort a Linked List Using Merge Sort

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list. Each node contains an integer value and a pointer t...

112.1k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0