### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

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.

### Problem Statement Understanding

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

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

1) We need to change the next pointer of N^{th}node to NULL.

2) Next pointer of last node (i.e. Last node of the doubly linked list) to head node.

3) prev of head node to last node.

4) 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). - 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.

1) Change the next pointer of Nth node to NULL.

2) Make next pointer of last node point to the head node

3) Make prev of head node point to the to last node.

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

### Code Implementation:

#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:** O(L), where L is the length of the linked list, as only one traversal of the linked list is required.

[forminator_quiz id=”4247″]

So, in this article, you have learnt how to rotate a doubly linked list by N nodes. This is an important coding interview question. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.