Rotate a Linked List

Rotate a Linked List
Rotate a Linked List

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.

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, Goldman Sachs, is “Rotate a Linked List.”

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.”

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 Codestudio before moving on to the solution.

Approach 1

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 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 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 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

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

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

This approach to rotate 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.

blog banner 1

Code

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

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 number of nodes in 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 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 the front of 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.

Key Takeaways

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!

If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at Code Studio.

Happy Learning! 

By: Pranchal Agrahari