Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach 1 - Efficiently Rotating a Linked List by K Positions
4.1.
Algorithm
4.2.
Code Implementation
4.3.
C++
4.4.
Java
4.5.
Python
4.6.
Output
5.
Approach 2 - Rotating a Singly Linked List by Converting to Circular Linked List
5.1.
Code Implementation
5.2.
C++
5.3.
Java
5.4.
Python
6.
Frequently Asked Questions
6.1.
Can a linked list be circular?
6.2.
How do you rotate a linked list counterclockwise?
6.3.
What is the time complexity for rotating a linked list?
6.4.
What does it mean to rotate a list? 
7.
Conclusion
Last Updated: Apr 18, 2024
Medium

Rotate a Linked List

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. The various elements in a linked list are linked together using pointers.

Rotating a LinkedList

Linked List is one of the important topics from an interview perspective. Almost all the major companies ask questions related to Linked List in the initial stages. One of the most frequently asked questions by Top Product based companies, including Amazon, Flipkart, Adobe, and Goldman Sachs, is “Rotate a Linked List.”

Problem Statement

The problem statement is: Given a Linked List and an integer ‘K.’ Rotate the Linked List by ‘K’ positions in a clockwise direction from the last node.”

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

  1. If the head is equal to null or ‘K’ is equal to 0, return the Linked List head.
  2. Create a variable that will store the length of the linked list and initialize it to 1.
  3. Create a temporary node that will be used to find the length of the Linked List and initialize it to head.
  4. Run a loop while the temporary node next is not equal to null and increase the length by 1 on each iteration
  5. If the length is less than ‘K,’ then update ‘K’ as ‘K’ % length ( To make ‘K’ come in a range of 0 to length).
  6. Update ‘K’ as length - ‘K’ (To reach (‘K’+1)th node from the end).
  7. If ‘K’ is equal to the length, return the head.
  8. Create a variable count, which will be used to reach (‘K’ + 1)th node from the end and initialize it to 1.
  9. Create a node current that will store the current node of the Linked List and initialize it to head.
  10. Run a loop while the count is less than ‘K’ and the current node is not equal to ‘NULL.’
  11. If the node is equal to ‘NULL.,’, then return the head of the Linked List.
  12. Update temp->next as head and update head as current->next and current->next as ‘NULL.’
  13. Finally, return the ‘HEAD’ of the Linked List.

Code Implementation

  • C++
  • Java
  • Python

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);
}

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);
}
}

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)

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++
  • Java
  • Python

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);
}

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);
}
}

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)

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! 

Previous article
Length of the Loop in the Linked List
Next article
Flatten a Linked List
Live masterclass