Example
For example, consider the given linked list is 1 -> 2 -> 3 -> 4 and K is 2 then the modified linked list after K rotation is 3 -> 4 -> 1-> 2. Notice that we have moved two-node from last to the front of the linked list
Recommended: Please solve it on Coding Ninjas Studio before moving on to the solution.
Approach 1 - Efficiently Rotating a Linked List by K Positions
To rotate a linked list by K position first thing that comes to mind is to move the K node from the back of the linked list to the front of the linked list, but there’s a problem in this approach if K is greater than the length of linked list then we will be moving same nodes multiple times so firstly we will check that whether K is smaller than the length of the linked list or not. If K is greater than the length of the linked list, then take the modulo of K with the length of the linked list(K%length). Now we can move K nodes from the back of the linked list to the front. But it is more complicated to find K nodes from the end than finding nodes from the front, so we will find the subtract K from the length, and now the problem changes to moving nodes from the front of the linked list to the back, i.e., left rotation of linked list.
Algorithm
- If the head is equal to null or ‘K’ is equal to 0, return the Linked List head.
- Create a variable that will store the length of the linked list and initialize it to 1.
- Create a temporary node that will be used to find the length of the Linked List and initialize it to head.
- Run a loop while the temporary node next is not equal to null and increase the length by 1 on each iteration
- If the length is less than ‘K,’ then update ‘K’ as ‘K’ % length ( To make ‘K’ come in a range of 0 to length).
- Update ‘K’ as length - ‘K’ (To reach (‘K’+1)th node from the end).
- If ‘K’ is equal to the length, return the head.
- Create a variable count, which will be used to reach (‘K’ + 1)th node from the end and initialize it to 1.
- Create a node current that will store the current node of the Linked List and initialize it to head.
- Run a loop while the count is less than ‘K’ and the current node is not equal to ‘NULL.’
- If the node is equal to ‘NULL.,’, then return the head of the Linked List.
- Update temp->next as head and update head as current->next and current->next as ‘NULL.’
- Finally, return the ‘HEAD’ of the Linked List.
Code Implementation
C++
//C++ program to rotate a linked list
#include<iostream>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
//Function to rotate a linked list
Node *rotate(Node *head, int k) {
// Base condition.
if(head == NULL) {
return head;
}
int len = 1;
Node *temp = head;
// Calculate length of the linked list.
while(temp->next != NULL) {
temp = temp->next;
len += 1;
}
// If k is greater than k bring it inthe . Ifrange of 0 - len.
if(len < k) {
k = k % len;
}
k = len - k;
// Number of rotations are same as len so no change in LL.
if(k == len || k == 0) {
return head;
}
int count = 1;
Node *current = head;
while(count < k && current != NULL) {
current = current->next;
count += 1;
}
if(current == NULL) {
return head;
}
// Changing pointers.
temp->next = head;
head = current->next;
current->next = NULL;
return head;
}
//Function to take Linked list input
void input(Node ** head,int data)
{
Node* temp=new Node();
temp->data=data;
temp->next=(*head);
(*head)=temp;
}
//function to print linked list
void printlist(Node* head)
{
while(head!=NULL)
{
cout<<head->data<<" " ;
head=head->next;
}
cout<<endl;
}
int main()
{
//taking input for linked list
Node* head=NULL;
//Creating a linked list 1->2->3->4->5
input(&head,5);
input(&head,4);
input(&head,3);
input(&head,2);
input(&head,1);
int k=2;
cout<<"Original linked list \n";
printlist(head);
head=rotate(head,k);
cout<<"Linked list after rotation \n";
printlist(head);
}
You can also try this code with Online C++ Compiler
Java
// Java program to rotate a linked list
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class RotateLinkedList {
// Function to rotate a linked list
static Node rotate(Node head, int k) {
if (head == null) {
return head;
}
int len = 1;
Node temp = head;
// Calculate length of the linked list
while (temp.next != null) {
temp = temp.next;
len++;
}
// If k is greater than len, bring it within range of 0 - len
if (len < k) {
k = k % len;
}
k = len - k;
// If k is 0 or equal to len, no change in linked list
if (k == len || k == 0) {
return head;
}
int count = 1;
Node current = head;
// Find the kth node
while (count < k && current != null) {
current = current.next;
count++;
}
if (current == null) {
return head;
}
// Change pointers
temp.next = head;
head = current.next;
current.next = null;
return head;
}
// Function to print linked list
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.next = new Node(4);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
int k = 2;
System.out.println("Original linked list:");
printList(head);
head = rotate(head, k);
System.out.println("Linked list after rotation:");
printList(head);
}
}
You can also try this code with Online Java Compiler
Python
# Python program to rotate a linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to rotate a linked list
def rotate(head, k):
if head is None:
return head
len = 1
temp = head
# Calculate length of the linked list
while temp.next is not None:
temp = temp.next
len += 1
# If k is greater than len, bring it within range of 0 - len
if len < k:
k = k % len
k = len - k
# If k is 0 or equal to len, no change in linked list
if k == len or k == 0:
return head
count = 1
current = head
# Find the kth node
while count < k and current is not None:
current = current.next
count += 1
if current is None:
return head
# Change pointers
temp.next = head
head = current.next
current.next = None
return head
# Function to print linked list
def printList(head):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
# Main function
if __name__ == "__main__":
head = Node(5)
head.next = Node(4)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(1)
k = 2
print("Original linked list:")
printList(head)
head = rotate(head, k)
print("Linked list after rotation:")
printList(head)
You can also try this code with Online Python Compiler
Output
Original linked list
1 2 3 4 5
Linked list after rotation
4 5 1 2 3
Time Complexity: O(n) where n is the number of nodes in the linked list
Space complexity: O(1)
Approach 2 - Rotating a Singly Linked List by Converting to Circular Linked List
This approach to rotating a linked list is similar to the previous one the only difference is that we will convert the singly linked list to a circular linked list and then move (length-K) nodes forward from the head node, making (length-K)th node’s next to null and next node as head.
Code Implementation
C++
//C++ program to rotate a linked list
#include<iostream>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
//Function to rotate a linked list
Node *rotate(Node *head, int k) {
// Base condition.
if(head == NULL) {
return head;
}
int len = 1;
Node *temp = head;
// Calculate length of the linked list.
while(temp->next != NULL) {
temp = temp->next;
len += 1;
}
k = k % len;
// Number of rotations are same as len so no change in LL.
if(k == len || k == 0) {
return head;
}
// To make a circular linked list.
temp->next = head;
temp = head;
for(int i = 0; i < abs(len - k - 1); i++) {
temp = temp->next;
}
// Changing pointers.
head = temp->next;
temp->next = NULL;
return head;
}
//Function to take Linked list input
void input(Node ** head,int data)
{
Node* temp=new Node();
temp->data=data;
temp->next=(*head);
(*head)=temp;
}
//function to print linked list
void printlist(Node* head)
{
while(head!=NULL)
{
cout<<head->data<<" " ;
head=head->next;
}
cout<<endl;
}
int main()
{
//taking input for linked list
Node* head=NULL;
//Creating a linked list 1->2->3->4->5
input(&head,5);
input(&head,4);
input(&head,3);
input(&head,2);
input(&head,1);
int k=2;
cout<<"Original linked list \n";
printlist(head);
head=rotate(head,k);
cout<<"Linked list after rotation \n";
printlist(head);
}
You can also try this code with Online C++ Compiler
Java
// Java program to rotate a linked list
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class RotateLinkedList {
// Function to rotate a linked list
static Node rotate(Node head, int k) {
if (head == null) {
return head;
}
int len = 1;
Node temp = head;
// Calculate length of the linked list
while (temp.next != null) {
temp = temp.next;
len++;
}
k = k % len;
// If k is 0 or equal to len, no change in linked list
if (k == 0) {
return head;
}
// To make a circular linked list
temp.next = head;
temp = head;
// Find the (len - k - 1)th node
for (int i = 0; i < len - k - 1; i++) {
temp = temp.next;
}
// Changing pointers
head = temp.next;
temp.next = null;
return head;
}
// Function to print linked list
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.next = new Node(4);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
int k = 2;
System.out.println("Original linked list:");
printList(head);
head = rotate(head, k);
System.out.println("Linked list after rotation:");
printList(head);
}
}
You can also try this code with Online Java Compiler
Python
# Python program to rotate a linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to rotate a linked list
def rotate(head, k):
if head is None:
return head
len = 1
temp = head
# Calculate length of the linked list
while temp.next is not None:
temp = temp.next
len += 1
k = k % len
# If k is 0, no change in linked list
if k == 0:
return head
# To make a circular linked list
temp.next = head
temp = head
# Find the (len - k - 1)th node
for i in range(len - k - 1):
temp = temp.next
# Changing pointers
head = temp.next
temp.next = None
return head
# Function to print linked list
def printList(head):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
# Main function
if __name__ == "__main__":
head = Node(5)
head.next = Node(4)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(1)
k = 2
print("Original linked list:")
printList(head)
head = rotate(head, k)
print("Linked list after rotation:")
printList(head)
You can also try this code with Online Python Compiler
Output
Original linked list
1 2 3 4 5
Linked list after rotation
4 5 1 2 3
Time Complexity: O(n) where n is the number of nodes in a linked list
Space complexity: O(1)
Frequently Asked Questions
Can a linked list be circular?
Yes, a linked list can be circular in a circular linked list the last node points to the first node instead of NULL.
How do you rotate a linked list counterclockwise?
To rotate a linked list counterclockwise, move the last node to the front by changing pointers accordingly, preserving the original order.
What is the time complexity for rotating a linked list?
The time complexity for rotating a linked list is O(n), where n is the number of nodes in the linked list.
What does it mean to rotate a list?
Rotating a linked list means considering a linked list as a circular structure and moving the node clock or anti-clockwise according to the requirement.
Conclusion
This blog discussed a very frequently asked interview problem, “Rotate a linked list.” The blog discussed two methods to solve this problem with algorithms and code in c++ if you want to master the linked list then check out this article.
If you are a beginner in coding and want to learn DSA, you can look out for our guided path for DSA, which is absolutely free!
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
To study more about Linked Lists, refer to Applications Of Linked Lists.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Learning!
46+ registered 