The Linked list is an important topic from an interview perspective. Companies like Amazon, Flipkart, Goldman Sach, Abode, Samsung, and many more asked questions over the linked lists. In this blog, we will discuss the famous problem of the linked list “rotate a linked list”. Let’s understand the problem statement of rotate a linked list for better understanding.
How to Rotate a Linked List
In this question, we are given a singly linked list and an integer X. We have to rotate the list counter-clockwise by X nodes.
Note: X is smaller than the count of nodes in the linked list.
Let’s try to understand the problem statement with the help of an example.
Suppose the given linked list 1 → 2 → 5 → 10 – 12 → 13, and the value of X is 4. Now, we have to rotate the given list counter-clockwise by X.
Here, rotating counter-clockwise a linked list by X means that the first X nodes of the linked list will be removed from the start and get appended to the end of the list.
In the given list, the first 4 nodes are 1 → 2 → 5 → 10. Now, these 4 elements will get appended to the end of the list. So, the final list will be:
12 → 13 → 1 → 2 → 5 → 10.
In this way, we are rotating the given first X nodes counter-clockwise.
Input :
Output :
Explanation : As the value of X is 4, so the first 4 nodes have been removed from the beginning of the linked list and appended at the end of the linked list.
Now, I think from the above example, it is clear what we have to do in this problem. So let’s move to approach.
Before directly jumping to approach in the next section, just try to think how will approach this problem?
It’s okay if your solution is not the best-optimized solution, we will try to optimize it together.
This question is not a very complex one. We are going to make use of linked list traversal in this question. Let us have a glance at the approach.
Approach and Algorithm of rotate a linked list
The approach is going to be pretty simple.
Let us first think about what we need to perform the required task of rotating the list counter-clockwise by X nodes.
- For linked list rotation, we have to change the next of Xth node to NULL, next of the last node to the head node, and finally, make the head point to the (X+1)th node.
- So, we need Xth node, (X+1)th node and the last node.
To acheive the above objective of rotation:
- We will traverse through the list and stop at the Xth node.
- We will store the pointer to the Xth node.
- The (X+1)th node can be reached using the next of Xth node. Now, we will keep traversing the list till the last node, and change the pointers as stated below:
- Change the next of Xth node to NULL
- Next of the last node to the head node.
- And finally, make the head point to the (X+1)th node.
Dry Run of rotate a linked list
Code Implementation of rotate a linked list
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
void rotate(struct Node** head_ref, int k)
{
if (k == 0)
return;
struct Node* current = *head_ref;
int count = 1;
while (count < k && current != NULL) {
current = current->next;
count++;
}
if (current == NULL)
return;
struct Node* kthNode = current;
while (current->next != NULL)
current = current->next;
current->next = *head_ref;
*head_ref = kthNode->next;
kthNode->next = NULL;
}
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main(void)
{
struct Node* head = NULL;
for (int i = 60; i > 0; i -= 10)
push(&head, i);
printf("Given linked list \n");
printList(head);
rotate(&head, 4);
printf("\nRotated Linked list \n");
printList(head);
return (0);
}
#include <bits stdc++.h="">
using namespace std;
class Node {
public:
int data;
Node* next;
};
void rotate(Node** head_ref, int k)
{
if (k == 0)
return;
Node* current = *head_ref;
int count = 1;
while (count < k && current != NULL) {
current = current->next;
count++;
}
if (current == NULL)
return;
Node* kthNode = current;
while (current->next != NULL)
current = current->next;
current->next = *head_ref;
*head_ref = kthNode->next;
kthNode->next = NULL;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main(void)
{
Node* head = NULL;
push(&head, 13);
push(&head,12);
push(&head,10);
push(&head,5);
push(&head,2);
push(&head,1);
cout << "Given linked list \n";
printList(head);
rotate(&head, 4);
cout << "\nRotated Linked list \n";
printList(head);
return (0);
}
public class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void rotate(int k)
{
if (k == 0)
return;
Node current = head;
int count = 1;
while (count < k && current != null) {
current = current.next;
count++;
}
if (current == null)
return;
Node kthNode = current;
while (current.next != null)
current = current.next;
current.next = head;
head = kthNode.next;
kthNode.next = null;
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(13);
llist.push(12);
llist.push(10);
llist.push(5);
llist.push(2);
llist.push(1);
System.out.println("Given list");
llist.printList();
llist.rotate(4);
System.out.println("Rotated Linked List");
llist.printList();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while(temp):
print(temp.data, end=" ")
temp = temp.next
def rotate(self, k):
if k == 0:
return
current = self.head
count = 1
while(count <k and current is not None):
current = current.next
count += 1
if current is None:
return
kthNode = current
while(current.next is not None):
current = current.next
current.next = self.head
self.head = kthNode.next
kthNode.next = None
llist = LinkedList()
llist.push(13)
llist.push(12)
llist.push(10)
llist.push(5)
llist.push(2)
llist.push(1)
print("Given linked list")
llist.printList()
llist.rotate(4)
print("\nRotated Linked list")
llist.printList()
Output
Given linked list: 1 2 5 10 12 13
Rotated Linked list: 12 13 1 2 5 10 Time Complexity rotate a linked list: O(n), as list traversal is needed.
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, C++, Java, and python. If you want to master the linked list then check out this article.
If you want to solve more questions on Linked List, which our expert mentors at PrepBytes curate, you can follow this link Linked List.
FAQs related to Rotate Linked list
1. 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.
2. How do I rotate a list?
To rotate a linked list, you need to move the nodes of the linked list in the clock or counter-clockwise; you can do so by moving nodes from front to back or moving nodes from back to front of the linked list.
3. 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.