The problem is to reverse the given doubly circular linked list.
Examples:
Input:
Output:
Algorithm:
insertEnd(head, new_node)
Declare last
if head == NULL then
new_node->next = new_node->prev = new_node
head = new_node
return
last = head->prev
new_node->next = head
head->prev = new_node
new_node->prev = last
last->next = new_node
reverse(head)
Initialize new_head = NULL
Declare last
last = head->prev
Initialize curr = last, prev
while curr->prev != last
prev = curr->prev
insertEnd(&new_head, curr)
curr = prev
insertEnd(&new_head, curr)
return new_head
Explanation: The variable head in the parameter list of insertEnd() is a pointer to a pointer variable. reverse() traverses the doubly circular linked list starting with the head pointer in the backward direction and one by one gets the node in the traversal. It inserts those nodes at the end of the list that starts with the new_head pointer with the help of the function insertEnd() and finally returns the new_head.
Implementation:
C++
// C++ implementation to reverse a// doubly circular linked list#include <bits/stdc++.h>using namespace std;// structure of a node of linked liststruct Node { int data; Node *next, *prev;};// function to create and return a new nodeNode* getNode(int data){ Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; return newNode;}// Function to insert at the endvoid insertEnd(Node** head, Node* new_node){ // If the list is empty, create a single node // circular and doubly list if (*head == NULL) { new_node->next = new_node->prev = new_node; *head = new_node; return; } // If list is not empty /* Find last node */ Node* last = (*head)->prev; // Start is going to be next of new_node new_node->next = *head; // Make new node previous of start (*head)->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node;}// Utility function to reverse a// doubly circular linked listNode* reverse(Node* head){ if (!head) return NULL; // Initialize a new head pointer Node* new_head = NULL; // get pointer to the last node Node* last = head->prev; // set 'curr' to last node Node *curr = last, *prev; // traverse list in backward direction while (curr->prev != last) { prev = curr->prev; // insert 'curr' at the end of the list // starting with the 'new_head' pointer insertEnd(&new_head, curr); curr = prev; } insertEnd(&new_head, curr); // head pointer of the reversed list return new_head;}// function to display a doubly circular list in// forward and backward directionvoid display(Node* head){ if (!head) return; Node* temp = head; cout << "Forward direction: "; while (temp->next != head) { cout << temp->data << " "; temp = temp->next; } cout << temp->data; Node* last = head->prev; temp = last; cout << "\nBackward direction: "; while (temp->prev != last) { cout << temp->data << " "; temp = temp->prev; } cout << temp->data;}// Driver program to test aboveint main(){ Node* head = NULL; insertEnd(&head, getNode(1)); insertEnd(&head, getNode(2)); insertEnd(&head, getNode(3)); insertEnd(&head, getNode(4)); insertEnd(&head, getNode(5)); cout << "Current list:\n"; display(head); head = reverse(head); cout << "\n\nReversed list:\n"; display(head); return 0;} |
Java
// Java implementation to reverse a // doubly circular linked list class GFG{// structure of a node of linked list static class Node{ int data; Node next, prev; }; // function to create and return a new node static Node getNode(int data) { Node newNode = new Node(); newNode.data = data; return newNode; } // Function to insert at the end static Node insertEnd(Node head, Node new_node) { // If the list is empty, create a single node // circular and doubly list if (head == null) { new_node.next = new_node.prev = new_node; head = new_node; return head; } // If list is not empty // Find last node / Node last = (head).prev; // Start is going to be next of new_node new_node.next = head; // Make new node previous of start (head).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return head;} // Utility function to reverse a // doubly circular linked list static Node reverse(Node head) { if (head==null) return null; // Initialize a new head pointer Node new_head = null; // get pointer to the last node Node last = head.prev; // set 'curr' to last node Node curr = last, prev; // traverse list in backward direction while (curr.prev != last) { prev = curr.prev; // insert 'curr' at the end of the list // starting with the 'new_head' pointer new_head=insertEnd(new_head, curr); curr = prev; } new_head=insertEnd(new_head, curr); // head pointer of the reversed list return new_head; } // function to display a doubly circular list in // forward and backward direction static void display(Node head) { if (head==null) return; Node temp = head; System.out.print( "Forward direction: "); while (temp.next != head) { System.out.print( temp.data + " "); temp = temp.next; } System.out.print( temp.data + " "); Node last = head.prev; temp = last; System.out.print( "\nBackward direction: "); while (temp.prev != last) { System.out.print( temp.data + " "); temp = temp.prev; } System.out.print( temp.data + " "); } // Driver code public static void main(String args[]){ Node head = null; head =insertEnd(head, getNode(1)); head =insertEnd(head, getNode(2)); head =insertEnd(head, getNode(3)); head =insertEnd(head, getNode(4)); head =insertEnd(head, getNode(5)); System.out.print( "Current list:\n"); display(head); head = reverse(head); System.out.print( "\n\nReversed list:\n"); display(head); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to reverse a# doubly circular linked listimport math# structure of a node of linked listclass Node: def __init__(self, data): self.data = data self.next = None# function to create and return a new nodedef getNode(data): newNode = Node(data) newNode.data = data return newNode# Function to insert at the enddef insertEnd(head, new_node): # If the list is empty, create a single node # circular and doubly list if (head == None) : new_node.next = new_node new_node.prev = new_node head = new_node return head # If list is not empty # Find last node last = head.prev # Start is going to be next of new_node new_node.next = head # Make new node previous of start head.prev = new_node # Make last previous of new node new_node.prev = last # Make new node next of old last last.next = new_node return head# Utility function to reverse a# doubly circular linked listdef reverse(head): if (head == None): return None # Initialize a new head pointer new_head = None # get pointer to the last node last = head.prev # set 'curr' to last node curr = last #*prev # traverse list in backward direction while (curr.prev != last): prev = curr.prev # insert 'curr' at the end of the list # starting with the 'new_head' pointer new_head = insertEnd(new_head, curr) curr = prev new_head = insertEnd(new_head, curr) # head pointer of the reversed list return new_head# function to display a doubly circular list in# forward and backward directiondef display(head): if (head == None): return temp = head print("Forward direction: ", end = "") while (temp.next != head): print(temp.data, end = " ") temp = temp.next print(temp.data) last = head.prev temp = last print("Backward direction: ", end = "") while (temp.prev != last): print(temp.data, end = " ") temp = temp.prev print(temp.data)# Driver Codeif __name__=='__main__': head = None head = insertEnd(head, getNode(1)) head = insertEnd(head, getNode(2)) head = insertEnd(head, getNode(3)) head = insertEnd(head, getNode(4)) head = insertEnd(head, getNode(5)) print("Current list:") display(head) head = reverse(head) print("\nReversed list:") display(head)# This code is contributed by Srathore |
C#
// C# implementation to reverse a // doubly circular linked listusing System;class GFG { // structure of a node of linked list public class Node { public int data; public Node next, prev; }; // function to create and return a new node static Node getNode(int data) { Node newNode = new Node(); newNode.data = data; return newNode; } // Function to insert at the end static Node insertEnd(Node head, Node new_node) { // If the list is empty, create a single node // circular and doubly list if (head == null) { new_node.next = new_node.prev = new_node; head = new_node; return head; } // If list is not empty // Find last node / Node last = (head).prev; // Start is going to be next of new_node new_node.next = head; // Make new node previous of start (head).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return head; } // Utility function to reverse a // doubly circular linked list static Node reverse(Node head) { if (head == null) return null; // Initialize a new head pointer Node new_head = null; // get pointer to the last node Node last = head.prev; // set 'curr' to last node Node curr = last, prev; // traverse list in backward direction while (curr.prev != last) { prev = curr.prev; // insert 'curr' at the end of the list // starting with the 'new_head' pointer new_head=insertEnd(new_head, curr); curr = prev; } new_head=insertEnd(new_head, curr); // head pointer of the reversed list return new_head; } // function to display a doubly circular list in // forward and backward direction static void display(Node head) { if (head == null) return; Node temp = head; Console.Write( "Forward direction: "); while (temp.next != head) { Console.Write( temp.data + " "); temp = temp.next; } Console.Write( temp.data + " "); Node last = head.prev; temp = last; Console.Write( "\nBackward direction: "); while (temp.prev != last) { Console.Write( temp.data + " "); temp = temp.prev; } Console.Write( temp.data + " "); } // Driver code public static void Main(String []args) { Node head = null; head = insertEnd(head, getNode(1)); head = insertEnd(head, getNode(2)); head = insertEnd(head, getNode(3)); head = insertEnd(head, getNode(4)); head = insertEnd(head, getNode(5)); Console.Write( "Current list:\n"); display(head); head = reverse(head); Console.Write( "\n\nReversed list:\n"); display(head); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to reverse a // doubly circular linked list // structure of a node of linked list class Node { constructor() { this.data = 0; this.next = null; this.prev = null; } } // function to create and return a new node function getNode(data) { var newNode = new Node(); newNode.data = data; return newNode; } // Function to insert at the end function insertEnd(head, new_node) { // If the list is empty, create a single node // circular and doubly list if (head == null) { new_node.next = new_node.prev = new_node; head = new_node; return head; } // If list is not empty // Find last node / var last = head.prev; // Start is going to be next of new_node new_node.next = head; // Make new node previous of start head.prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return head; } // Utility function to reverse a // doubly circular linked list function reverse(head) { if (head == null) return null; // Initialize a new head pointer var new_head = null; // get pointer to the last node var last = head.prev; // set 'curr' to last node var curr = last, prev; // traverse list in backward direction while (curr.prev != last) { prev = curr.prev; // insert 'curr' at the end of the list // starting with the 'new_head' pointer new_head = insertEnd(new_head, curr); curr = prev; } new_head = insertEnd(new_head, curr); // head pointer of the reversed list return new_head; } // function to display a doubly circular list in // forward and backward direction function display(head) { if (head == null) return; var temp = head; document.write("Forward direction: "); while (temp.next != head) { document.write(temp.data + " "); temp = temp.next; } document.write(temp.data + " "); var last = head.prev; temp = last; document.write("<br>Backward direction: "); while (temp.prev != last) { document.write(temp.data + " "); temp = temp.prev; } document.write(temp.data + " "); } // Driver code var head = null; head = insertEnd(head, getNode(1)); head = insertEnd(head, getNode(2)); head = insertEnd(head, getNode(3)); head = insertEnd(head, getNode(4)); head = insertEnd(head, getNode(5)); document.write("Current list:<br>"); display(head); head = reverse(head); document.write("<br><br>Reversed list:<br>"); display(head); </script> |
Output
Current list: Forward direction: 1 2 3 4 5 Backward direction: 5 4 3 2 1 Reversed list: Forward direction: 5 4 3 2 1 Backward direction: 1 2 3 4 5
Complexity Analysis:
- Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
- Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
