Rotate Doubly Linked List by N nodes

Riya
Last Updated: May 13, 2022

Introduction-  

This article will discuss the problem “Rotate doubly linked list by N nodes” and its solution. Before jumping into the details of the problem and approach to solve it, you need to know about the doubly linked list data structure.


Now, let’s understand the problem. In this problem, a doubly linked list and a value ‘N’ are given, and we have to rotate the given doubly linked list counterclockwise by ‘N’ nodes where ‘N’ is less than the number of nodes in the given linked list.

 

Let’s make it more clear by taking an example.

Assume the given linked list is : 1 <-> 4 <-> 5 <-> 9 <-> 8 <-> 5 <-> 2

and given N = 3

After rotating the given doubly linked list by three nodes, we will get the following doubly linked list:

 9 <-> 8 <-> 5 <-> 2 <-> 1 <-> 4 <-> 5

 

Solution Approach 

We have to rotate doubly linked list by N nodes in a counterclockwise direction. So, our approach is first to join the last node to the first node to get counterclockwise rotation. And then, using two pointers, go to the Nth node and last node of the linked list with respect to the Nth node. So, finally, these two pointers will be pointing to the first and last node of the rotated linked list. So, after this, remove the link between the first and last nodes of the rotated linked list and then return the pointer pointing to the first node.

 

Let’s understand using the example that we used in the “Introduction” section.

 

Given doubly linked list : 1 <-> 4 <-> 5 <-> 9 <-> 8 <-> 5 <-> 2

and N = 3

So, first, after joining the first and last nodes of the linked list, we will get the below circular linked list -

Now the head is pointing to 1, and last_node is pointing to 2. After moving the head and last node pointer by 3 (as N = 3), the head will point to 9, and the last node will point to the 5 occurring first in the original linked list from the head node side. 

So, next, after removing the link between the first and last node, we will get the below required rotated doubly linked list. 

     9 <-> 8 <-> 5 <-> 2 <-> 1 <-> 4 <-> 5

 

Algorithm -

Step 1. Create a class ‘Node’ for creating the doubly linked lists.

Step 2. Then create the function “rotate()” to rotate doubly linked list by N nodes, which will take two inputs - the pointer pointing to the given doubly linked list's head node and the given value ‘N’ by which we have to rotate the given linked list in the counterclockwise direction.

Inside the function, create a pointer “last_node” and use it inside a while loop to get the last node of the linked list.

Step 3.  Now join the first and last node so that we can get a counterclockwise rotation. And then, traverse to the Nth node and take the “head” and the “last_node” pointer to point to the first and last node of the rotated linked list.

Step 4. Finally, remove the link between the first and last node of the rotated linked list and return the head node.

Step 5. Also, create two helper functions - one for inserting the nodes in the linked list to generate a doubly linked list and another for printing the doubly linked list.
 

C++ code:

// C++ code to rotate doubly linked list by N nodes
#include <bits/stdc++.h>
using namespace std;

// Class to create the nodes of the doubly linked list
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int data)
  {
   this->data = data;
   this->prev = NULL;
   this->next = NULL;
  }
};

// Function to add nodes in beginning of the linked list
void addNode(Node** head_ref, int val)
{
    Node* new_node = new Node(val);
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    *head_ref = new_node;
}

// Function to print the linked list
void printList(Node* node)
{
    while (node->next != NULL) 
    {
        if(node->next != NULL) {
              cout << node->data << " <-> ";
        }
        else {
               cout<< node->data <<endl;
        }
        node = node->next;
    }
    cout << node->data;
}

// Function to rotate doubly linked list by N nodes
Node* rotate(Node* head, int N)
  {
   // If we have to rotate by zero nodes, then return the head node as it is
   if(N==0) return head;
  
   // Creating a node to point the last node of the linked list
   Node* last_node = head;
   while(last_node->next != NULL)
     {
      last_node = last_node->next;
     }
     
   /*
          Join the first and last node by making the first node the next 
           of the last node and the last node as prev of the first node
   */
   last_node->next = head;
   head->prev = last_node;
  
   // Variable used to go to the Nth node
   int cnt=0;
   while(cnt < N)
     {
             head = head->next;
             last_node=last_node->next;
             cnt++;
     }
    
     /*
       Now head and last_node is pointing to the first and last node of
       the rotated inked, so now remove the link between head and last node
     */
     last_node->next=NULL;
     head->prev=NULL;
     
     // Finally, return the head node of the rotated linked list
     return head;
  }

int main()
  {
            /*
              Create the doubly linked list, which is to be rotated 
              counterclockwise by N nodes 
            */
    Node* head = NULL;
    addNode(&head, 2);
    addNode(&head, 5);
    addNode(&head, 8);
    addNode(&head, 9);
    addNode(&head, 5);
    addNode(&head, 4);
    addNode(&head, 1);
    
    cout<< "The doubly linked list before rotation "<< endl;
    printList(head);
    
    int N=3;
    // Call the function to rotate doubly linked list by N nodes
    head = rotate(head, N);
    
    cout<<endl<< "The doubly linked list after rotation "<< endl;
    printList(head);
  }   

 

Output:

The doubly linked list before rotation 
1 <-> 4 <-> 5 <-> 9 <-> 8 <-> 5 <-> 2
The doubly linked list after rotation 
9 <-> 8 <-> 5 <-> 2 <-> 1 <-> 4 <-> 5

 

Algorithm Complexity: 

Time Complexity: O(N)

In the function “rotate()” which is created to rotate doubly linked list by N nodes, we have traversed through all the nodes of the given linked list. So, the time complexity is O(N), where ‘N’ is the total number of nodes in the given doubly linked list.

 

Space Complexity: O(1) 

 We have used constant space. So, the space complexity is O(1).

 

Frequently asked questions-

  1. What is a linked list?
    A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).   
     
  2. What is the key difference between a singly linked list and a doubly-linked list?
    A singly-linked list is unidirectional, which means that the node of a singly linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.

 

Key takeaways-

This article discussed the “Rotate doubly linked list by N nodes” problem, discussed the approach to solve the problem, and discussed the time and space complexities. If you want to practice this problem, then you can visit codestudio.

 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

 

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
0 upvotes