CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to rotate doubly linked list by N nodes.ExplanationIn this program, we need to create a doubly linked list and rotate it by n node. This can be achieved by maintaining a pointer that starts from the head node and traverses the list until current points to the nth node. Move the list from head to the nth node and place it after tail. Now nth node will be the tail of the list and node next to nth node will be the new head. Here, n should always be greater than 0 but less than the size of the list. Original List: List after rotating it by 3 nodes: In the above example, we need to rotate list by 3 nodes. First, we iterate through the list until current points to the 3rd node which is, in this case, are node 3. Move the list from node 1 to 3 and place it after tail. Now, node 4 will be new head and node 3 will be the new tail. Algorithm
SolutionPython#Represent a node of doubly linked list class Node: def __init__(self,data): self.data = data; self.previous = None; self.next = None; class RotateList: #Represent the head and tail of the doubly linked list def __init__(self): self.head = None; self.tail = None; self.size = 0; #addNode() will add a node to the list def addNode(self, data): #Create a new node newNode = Node(data); #If list is empty if(self.head == None): #Both head and tail will point to newNode self.head = self.tail = newNode; #head's previous will point to None self.head.previous = None; #tail's next will point to None, as it is the last node of the list self.tail.next = None; else: #newNode will be added after tail such that tail's next will point to newNode self.tail.next = newNode; #newNode's previous will point to tail newNode.previous = self.tail; #newNode will become new tail self.tail = newNode; #As it is last node, tail's next will point to None self.tail.next = None; #Size will count the number of nodes present in the list self.size = self.size + 1; #rotateList() will rotate the list by given n nodes def rotateList(self, n): #Initially, current will point to head current = self.head; #n should not be 0 or greater than or equal to number of nodes present in the list if(n == 0 or n >= self.size): return; else: #Traverse through the list till current point to nth node #after this loop, current will point to nth node for i in range(1, n): current = current.next; #Now to move entire list from head to nth node and add it after tail self.tail.next = self.head; #Node next to nth node will be new head self.head = current.next; #Previous node to head should be None self.head.previous = None; #nth node will become new tail of the list self.tail = current; #tail's next will point to None self.tail.next = None; #display() will print out the nodes of the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print("List is empty"); return; while(current != None): #Prints each node by incrementing pointer. print(current.data), current = current.next; print(); dList = RotateList(); #Add nodes to the list dList.addNode(1); dList.addNode(2); dList.addNode(3); dList.addNode(4); dList.addNode(5); print("Original List: "); dList.display(); #Rotates list by 3 nodes dList.rotateList(3); print("Updated List: "); dList.display(); Output: Original List: 1 2 3 4 5 Updated List: 4 5 1 2 3 C#include <stdio.h> //Represent a node of the doubly linked list struct node{ int data; struct node *previous; struct node *next; }; int size = 0; //Represent the head and tail of the doubly linked list struct node *head, *tail = NULL; //addNode() will add a node to the list void addNode(int data) { //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode>data = data; //If list is empty if(head == NULL) { //Both head and tail will point to newNode head = tail = newNode; //head's previous will point to NULL head>previous = NULL; //tail's next will point to NULL, as it is the last node of the list tail>next = NULL; } else { //newNode will be added after tail such that tail's next will point to newNode tail>next = newNode; //newNode's previous will point to tail newNode>previous = tail; //newNode will become new tail tail = newNode; //As it is last node, tail's next will point to NULL tail>next = NULL; } //Size will count the number of nodes present in the list size++; } //rotateList() will rotate the list by given n nodes void rotateList(int n) { //Initially, current will point to head struct node *current = head; //n should not be 0 or greater than or equal to number of nodes present in the list if(n == 0  n >= size) return; else { //Traverse through the list till current point to nth node //after this loop, current will point to nth node for(int i = 1; i < n; i++) current = current>next; //Now to move entire list from head to nth node and add it after tail tail>next = head; //Node next to nth node will be new head head = current>next; //Previous node to head should be NULL head>previous = NULL; //nth node will become new tail of the list tail = current; //tail's next will point to NULL tail>next = NULL; } } //display() will print out the nodes of the list void display() { //Node current will point to head struct node *current = head; if(head == NULL) { printf("List is empty\n"); return; } while(current != NULL) { //Prints each node by incrementing pointer. printf("%d ", current>data); current = current>next; } printf("\n"); } int main() { //Add nodes to the list addNode(1); addNode(2); addNode(3); addNode(4); addNode(5); printf("Original List: \n"); display(); //Rotates list by 3 nodes rotateList(3); printf("Updated List: \n"); display(); return 0; } Output: Original List: 1 2 3 4 5 Updated List: 4 5 1 2 3 JAVApublic class RotateList { //Represent a node of the doubly linked list class Node{ int data; Node previous; Node next; public Node(int data) { this.data = data; } } int size = 0; //Represent the head and tail of the doubly linked list Node head, tail = null; //addNode() will add a node to the list public void addNode(int data) { //Create a new node Node newNode = new Node(data); //If list is empty if(head == null) { //Both head and tail will point to newNode head = tail = newNode; //head's previous will point to null head.previous = null; //tail's next will point to null, as it is the last node of the list tail.next = null; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode's previous will point to tail newNode.previous = tail; //newNode will become new tail tail = newNode; //As it is last node, tail's next will point to null tail.next = null; } //Size will count the number of nodes present in the list size++; } //rotateList() will rotate the list by given n nodes public void rotateList(int n) { //Initially, current will point to head Node current = head; //n should not be 0 or greater than or equal to number of nodes present in the list if(n == 0  n >= size) return; else { //Traverse through the list till current point to nth node //after this loop, current will point to nth node for(int i = 1; i < n; i++) current = current.next; //Now to move entire list from head to nth node and add it after tail tail.next = head; //Node next to nth node will be new head head = current.next; //Previous node to head should be null head.previous = null; //nth node will become new tail of the list tail = current; //tail's next will point to null tail.next = null; } } //display() will print out the nodes of the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing the pointer. System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { RotateList dList = new RotateList(); //Add nodes to the list dList.addNode(1); dList.addNode(2); dList.addNode(3); dList.addNode(4); dList.addNode(5); System.out.println("Original List: "); dList.display(); //Rotates list by 3 nodes dList.rotateList(3); System.out.println("Updated List: "); dList.display(); } } Output: Original List: 1 2 3 4 5 Updated List: 4 5 1 2 3 C#using System; namespace DoublyLinkedList { public class Program { //Represent a node of the doubly linked list public class Node<T>{ public T data; public Node<T> previous; public Node<T> next; public Node(T value) { data = value; } } public class RotateList<T>{ int size = 0; //Represent the head and tail of the doubly linked list protected Node<T> head = null; protected Node<T> tail = null; //addNode() will add a node to the list public void addNode(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //If list is empty if(head == null) { //Both head and tail will point to newNode head = tail = newNode; //head's previous will point to null head.previous = null; //tail's next will point to null, as it is the last node of the list tail.next = null; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode's previous will point to tail newNode.previous = tail; //newNode will become new tail tail = newNode; //As it is last node, tail's next will point to null tail.next = null; } //Size will count the number of nodes present in the list size++; } //rotateList() will rotate the list by given n nodes public void rotateList(int n) { //Initially, current will point to head Node<T> current = head; //n should not be 0 or greater than or equal to number of nodes present in the list if(n == 0  n >= size) return; else { //Traverse through the list till current point to nth node //after this loop, current will point to nth node for(int i = 1; i < n; i++) current = current.next; //Now to move entire list from head to nth node and add it after tail tail.next = head; //Node next to nth node will be new head head = current.next; //Previous node to head should be null head.previous = null; //nth node will become new tail of the list tail = current; //tail's next will point to null tail.next = null; } } //display() will print out the nodes of the list public void display() { //Node current will point to head Node<T> current = head; if(head == null) { Console.WriteLine("List is empty"); return; } while(current != null) { //Prints each node by incrementing the pointer. Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } } public static void Main() { RotateList<int> dList = new RotateList<int>(); //Add nodes to the list dList.addNode(1); dList.addNode(2); dList.addNode(3); dList.addNode(4); dList.addNode(5); Console.WriteLine("Original List: "); dList.display(); //Rotates list by 3 nodes dList.rotateList(3); Console.WriteLine("Updated List: "); dList.display(); } } } Output: Original List: 1 2 3 4 5 Updated List: 4 5 1 2 3 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of doubly linked list class Node{ public $data; public $previous; public $next; function __construct($data){ $this>data = $data; } } class RotateList{ //Represent the head and tail of the doubly linked list public $head; public $tail; public $size = 0; function __construct(){ $this>head = NULL; $this>tail = NULL; $this>size = 0; } //addNode() will add a node to the list function addNode($data){ //Create a new node $newNode = new Node($data); //If list is empty if($this>head == NULL) { //Both head and tail will point to newNode $this>head = $this>tail = $newNode; //head's previous will point to NULL $this>head>previous = NULL; //tail's next will point to NULL, as it is the last node of the list $this>tail>next = NULL; } else { //newNode will be added after tail such that tail's next will point to newNode $this>tail>next = $newNode; //newNode's previous will point to tail $newNode>previous = $this>tail; //newNode will become new tail $this>tail = $newNode; //As it is last node, tail's next will point to NULL $this>tail>next = NULL; } //Size will count the number of nodes present in the list $this>size++; } //rotateList() will rotate the list by given n nodes function rotateList($n) { //Initially, current will point to head $current = $this>head; //n should not be 0 or greater than or equal to number of nodes present in the list if($n == 0  $n >= $this>size) return; else { //Traverse through the list till current point to nth node //after this loop, current will point to nth node for($i = 1; $i < $n; $i++) $current = $current>next; //Now to move entire list from head to nth node and add it after tail $this>tail>next = $this>head; //Node next to nth node will be new head $this>head = $current>next; //Previous node to head should be NULL $this>head>previous = NULL; //nth node will become new tail of the list $this>tail = $current; //tail's next will point to NULL $this>tail>next = NULL; } } //display() will print out the nodes of the list function display() { //Node current will point to head $current = $this>head; if($this>head == NULL) { print("List is empty <br>"); return; } while($current != NULL) { //Prints each node by incrementing pointer. print($current>data . " "); $current = $current>next; } print("<br>"); } } $dList = new RotateList(); //Add nodes to the list $dList>addNode(1); $dList>addNode(2); $dList>addNode(3); $dList>addNode(4); $dList>addNode(5); print("Original List: <br>"); $dList>display(); //Rotates list by 3 nodes $dList>rotateList(3); print("Updated List: <br>"); $dList>display(); ?> </body> </html> Output: Original List: 1 2 3 4 5 Updated List: 4 5 1 2 3
Next Topic#
