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

Recommended Topic, __Floyds Algorithm__ and __Rabin Karp Algorithm__

## Solution Approach

We have to rotate the 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 the 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 the 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 a 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).