Last Updated on November 22, 2022 by Prepbytes

Most of the linked list questions are not that complicated as they seem because a normal logic can be applied. Lets just say we have to rotate doubly linked list by n nodes. To approach this code, we will simply make the last node pointed to the head of the first node and make it circular. And then we will remove the next pointer after n nodes and to make it un-circular. So, in this article, let’s get into the approach to rotate doubly linked list by n nodes.

## How to Rotate Doubly Linked List by N Nodes

In this problem, we have been given a doubly linked list. Our task is to rotate the linked list counter-clockwise by N nodes. Here, N is a given positive integer which is smaller than the total number of nodes in the doubly linked list.

Let’s try to understand the problem statement with help of examples.

For example, if the doubly linked list is:

and let’s assume N to be equal to 2.

So according to the problem statement now we have to rotate the doubly linked list counter-clockwise by 2 nodes. To do, so the nodes with value A and B will be removed from their original positions and will be inserted at the end of the linked list, which will yield us our final resultant linked list as:

Given list:

Rotated list:

Similarly, if we are given a linked list as:

It means that we will have to rotate the above doubly linked list counter-clockwise by 4 nodes. To do, so we will move the first 4 nodes from the beginning to the end of the list such that our final linked list will be:

#### Some more Examples

**Input:**

**Output:**

**Input:**

**Output:**

Now I think from the above examples it is clear what the problem is demanding. So next we have to think how we can approach this problem towards a solution?

Let’s have a glance at approach.

## Approach and Algorithm to rotate doubly linked list by n nodes

The approach is going to be pretty simple.

So let’s first think about what we actually need to perform the task of rotating a doubly linked list by N nodes.

- To rotate the doubly linked list by N nodes
- We need to change the next pointer of N
^{th}node to NULL. - Next pointer of last node (i.e. Last node of the doubly linked list) to head node.
- prev of head node to last node.
- And finally change head to (N+1)
^{th}node and prev of new head node to NULL (Since we know that in a doubly linked list, prev of head node is NULL).

- We need to change the next pointer of N
- So we basically need to get hold of these three nodes: N
^{th}node, (N+1)^{th}node and last node.

**To achieve the above objective of rotation:**

- Start traversing the list from the beginning and stop at the N
^{th}node. - Store the pointer to N
^{th}node so that we can get (N+1)^{th}node using NthNode->next. - We will keep traversing the list till the end of the list and store the pointer to the last node as well.
- Finally, we will change the pointers as stated below.
- Change the next pointer of Nth node to NULL.
- Make next pointer of last node point to the head node
- Make prev of head node point to the to last node.
- Finally, make (N+1)
^{th}node the new head and point the prev of new head node to NULL.

- Finally, following the above steps, our list will get rotated counter-clockwise by N nodes.

At last, print the rotated list using the PrintList function.

### Dry Run to rotate doubly linked list by n nodes

## Code Implementation to rotate doubly linked list by n nodes

#include#include struct Node { int data; struct Node* prev; struct Node* next; }; void rotate(struct Node** head_ref, int N) { if (N == 0) return; struct Node* current = *head_ref; int count = 1; while (count < N && current != NULL) { current = current->next; count++; } if (current == NULL) return; struct Node* NthNode = current; while (current->next != NULL) current = current->next; current->next = *head_ref; (*head_ref)->prev = current; *head_ref = NthNode->next; (*head_ref)->prev = NULL; NthNode->next = NULL; } void push(struct Node** head_ref, int new_c) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_c; new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) (*head_ref)->prev = new_node; *head_ref = new_node; } void printList(struct Node* node) { while (node->next != NULL) { printf("%d, ",node->data); node = node->next; } printf("%d ",node->data); } int main(void) { struct Node* head = NULL; push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int N = 2; printf( "Given linked list \n"); printList(head); rotate(&head, N); printf( "\nRotated Linked list \n"); printList(head); return 0; }

#includeusing namespace std; struct Node { int data; struct Node* prev; struct Node* next; }; void rotate(struct Node** head_ref, int N) { if (N == 0) return; struct Node* current = *head_ref; int count = 1; while (count < N && current != NULL) { current = current->next; count++; } if (current == NULL) return; struct Node* NthNode = current; while (current->next != NULL) current = current->next; current->next = *head_ref; (*head_ref)->prev = current; *head_ref = NthNode->next; (*head_ref)->prev = NULL; NthNode->next = NULL; } void push(struct Node** head_ref, int new_c) { struct Node* new_node = new Node; new_node->data = new_c; new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) (*head_ref)->prev = new_node; *head_ref = new_node; } void printList(struct Node* node) { while (node->next != NULL) { cout << node->data << " "; node = node->next; } cout << node->data; } int main(void) { struct Node* head = NULL; push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int N = 2; cout << "Given linked list \n"; printList(head); rotate(&head, N); cout << "\nRotated Linked list \n"; printList(head); return 0; }

class ReverseN { static class Node { int data; Node prev; Node next; } static Node head = null; static void rotate( int N) { if (N == 0) return; Node current = head; int count = 1; while (count < N && current != null) { current = current.next; count++; } if (current == null) return; Node NthNode = current; while (current.next != null) current = current.next; current.next = head; (head).prev = current; head = NthNode.next; (head).prev = null; NthNode.next = null; } static void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.prev = null; new_node.next = (head); if ((head) != null) (head).prev = new_node; head = new_node; } static void printList(Node node) { while (node != null && node.next != null) { System.out.print(node.data + " "); node = node.next; } if(node != null) System.out.print(node.data); } public static void main(String[] args) { push(5); push(4); push(3); push(2); push(1); int N = 2; System.out.println("Given linked list "); printList(head); System.out.println(); rotate(N); System.out.println("Rotated Linked list "); printList(head); } }

class Node: def __init__(self, next = None, prev = None, data = None): self.next = next self.prev = prev self.data = data def push(head, new_data): new_node = Node(data = new_data) new_node.next = head new_node.prev = None if head is not None: head.prev = new_node head = new_node return head def printList(head): node = head while(node is not None): print(node.data, end = " "), last = node node = node.next def rotate(head, N): if N == 0 : return current = head count = 1 while count < N and current != None : current = current.next count += 1 if current == None : return NthNode = current while current.next != None : current = current.next current.next = head head.prev = current head = NthNode.next head.prev = None NthNode.next = None return head if __name__ == "__main__": head = None head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) print("Given linked list") printList(head) print() N = 2 head = rotate(head, N) print("Rotated Linked list") printList(head)

```
Output:
Given linked list: 1 2 3 4 5
Rotated Linked list: 3 4 5 1 2
```

**Time Complexity to rotate doubly linked list by n nodes:** O(L), where L is the length of the linked list, as only one traversal of the linked list is required.

**Conclusion**

So, in this article, We have implemented a simple logic irrespective of how complex the question was. We basically made a linked list into a circular one then removed the link after n nodes to make it un-circular. So that is how we rotate doubly linked list by n nodes. Enthusiastic about more questions visit the link and find all questions of linked lists.Linked List.

## FAQs

**1. Why a doubly linked list is preferred than a singly linked list?**

Doubly linked list is a bi- directional list, which means it can be traversed through both sides. So, finding elements in a doubly linked list is far more easy.

**2. What is the time complexity of reversing a doubly linked list?**

The time complexity of reversing a doubly linked list is O(n).

**3. What is the most efficient way to reverse a doubly linked list?**

The iterative approach where we assign pointers, head, and current node as null and traverse through the lists.