El problema es invertir la lista enlazada doblemente circular dada.
Ejemplos:
Entrada:
Producción:
Algoritmo:
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
Explicación: El encabezado de la variable en la lista de parámetros de insertEnd() es un puntero a una variable de puntero. reverse() atraviesa la lista enlazada doblemente circular comenzando con el puntero de la cabeza en la dirección hacia atrás y uno por uno obtiene el Node en el recorrido. Inserta esos Nodes al final de la lista que comienza con el puntero new_head con la ayuda de la función insertEnd() y finalmente devuelve el new_head .
C++
// C++ implementation to reverse a
// doubly circular linked list
#include <bits/stdc++.h>
using namespace std;
// structure of a node of linked list
struct Node {
int data;
Node *next, *prev;
};
// function to create and return a new node
Node* getNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
return newNode;
}
// Function to insert at the end
void 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 list
Node* 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 direction
void 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 above
int 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 list
import math
# structure of a node of linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# function to create and return a new node
def getNode(data):
newNode = Node(data)
newNode.data = data
return newNode
# Function to insert at the end
def 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 list
def 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 direction
def 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 Code
if __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 list
using 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>
Producción:
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
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA