Linked List: Rotate Doubly linked list by N nodes

Problem Statement:

You are given a DLL and a integer N. You need to rotate the DLL counter clock wise

Example

Input  : a  b  c  d  e   
N = 2
Output : c  d  e  a  b 

Solution

The solution is very easy.

We need 3 pointer to hold 3 nodes: Nth node, (N+1) node and last node.

Traverse the list till the Nth node.

Store the pointer at Nth node and N+1 node.

Then keep traversing till the end and shore pointer to last node.

Now perform the below steps:

Now change the next of Nth node to null.

Next of last node to previous head node and prev of the head node to last node

Finally change head to (N+1) node and prev of new head node to NULL.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

struct Node 
{ 
    int data; 
    struct Node* prev; 
    struct Node* next; 
}; 
  

void rotate_n_times(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_data) 
{ 
    struct Node* new_node =  new Node; 
    new_node->data = new_data; 
    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_n_times(&head, N); 
  
    cout << "\nRotated Linked list \n"; 
    printList(head); 
  
    return 0; 
} 

Output:

Given linked list
1 <=> 2 <=> 3 <=> 4 <=> 5
Rotated Linked list
3 <=> 4 <=> 5 <=> 1 <=> 2