Program to Rotate Doubly linked list by N nodes in C++

In this tutorial, we are going to learn about the Program to Rotate Doubly linked list by N nodes in C++. Firstly, we will learn about the doubly linked list.

Introduction

A doubly linked list is a type of linked list in which a node contains two pointers. One for the previous as well as the next node in the sequence. Therefore, in a doubly-linked list, a node has three parts: data, a pointer to the next node in sequence (nxt pointer), a pointer to the previous node (prev pointer).

We need to reach three nodes: Nth node, (N+1)th node and last node. To get the Nth node traverse the list from the beginning and stop at Nth node. Store the pointer to Nth node. To reach (N+1)th node using NthNode->next. Getting the last element is easy just keep on traversing till the next of current pointer is NULL. Then this node is last just store it.

C++ Program to rotate doubly-linked list by ‘N’ Nodes

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    char 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_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; 
    int t,pos;
    char ch;
    
    cout<<"Enter the number of elements to be inserted : ";
    cin>>t;
    
    for(int i=0;i<t;i++){
    	cin>>ch;
    	push(&head, ch);
  }
  
  cout<<"Enter the positon from which you want to rotate : ";
  cin>>pos;
  
  if(pos <= t){
    
    cout << "Given linked list \n"; 
    printList(head); 
    rotate(&head, pos); 
  
    cout << "\nRotated Linked list \n"; 
    printList(head); 
    
  }
  
    return 0; 
}

INPUT & OUTPUT :

Enter the number of elements to be inserted : 6
y
o
g
i
d
o
Enter the positon from which you want to rotate : 3
Given linked list
o <=> d <=> i <=> g <=> o <=> y
Rotated Linked list
g <=> o <=> y <=> o <=> d <=> i

In the above code, we have given input of different characters and then the number of elements to be rotated.

The output shows both the entered list and then the rotated list.

The same technique can be used to rotate the list in the opposite direction.

Also Checkout :

How to make a folder using C++

Leave a Reply

Your email address will not be published. Required fields are marked *