Dada una lista doblemente enlazada , la tarea es invertir la lista doblemente enlazada dada.
Vea los diagramas a continuación, por ejemplo.
(a) Original Doubly Linked List
(b) Reversed Doubly Linked List
Aquí hay un método simple para invertir una lista doblemente enlazada. Todo lo que tenemos que hacer es intercambiar los punteros anterior y siguiente para todos los Nodes, cambiar la anterior del encabezado (o inicio) y cambiar el puntero del encabezado al final.
C++
/* C++ program to reverse a doubly
linked list */
#include <bits/stdc++.h>
using namespace std;
// A node of the doubly linked list
class Node
{
public:
int data;
Node *next;
Node *prev;
};
/* Function to reverse a Doubly
Linked List */
void reverse(Node **head_ref)
{
Node *temp = NULL;
Node *current = *head_ref;
/* Swap next and prev for all nodes of
doubly linked list */
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
/* Before changing the head, check for
the cases like empty list and list
with only one node */
if(temp != NULL )
*head_ref = temp->prev;
}
// UTILITY FUNCTIONS
/* Function to insert a node at the
beginning of the Doubly Linked List */
void push(Node** head_ref, int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
/* Since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* Link the old list off the
new node */
new_node->next = (*head_ref);
/* Change prev of head node to
new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
/* Move the head to point to the
new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given
doubly linked list. This function is
same as printList() of singly linked list */
void printList(Node *node)
{
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
/* Let us create a sorted linked list
to test the functions. Created linked
list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout <<
"Original Linked list" << endl;
printList(head);
// Reverse doubly linked list
reverse(&head);
cout <<
"Reversed Linked list" << endl;
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10
Complejidad temporal: O(N), donde N denota el número de Nodes en la lista doblemente enlazada.
Espacio auxiliar: O(1)
También podemos intercambiar datos en lugar de punteros para invertir la lista doblemente enlazada. El método utilizado para invertir la array se puede utilizar para intercambiar datos. El intercambio de datos puede ser costoso en comparación con los punteros si el tamaño de los elementos de datos es mayor.
Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto o encuentra mejores formas de resolver el mismo problema.
Método 2:
La misma pregunta también se puede hacer usando Stacks.
Pasos:
- Siga empujando los datos del Node en la pila. -> O(n)
- Sigue sacando los elementos y actualizando la lista doblemente enlazada
C++
// C++ program to reverse a doubly linked list
#include <bits/stdc++.h>
using namespace std;
struct LinkedList
{
struct Node
{
int data;
Node *next, *prev;
Node(int d)
{
data = d;
next = prev = NULL;
}
};
Node* head = NULL;
/* Function to reverse a Doubly Linked
List using Stacks */
void reverse()
{
stack<int> st;
Node* temp = head;
while (temp != NULL)
{
st.push(temp->data);
temp = temp->next;
}
// Added all the elements sequence
// wise in the set
temp = head;
while (temp != NULL)
{
temp->data = st.top();
st.pop();
temp = temp->next;
}
// Popped all the elements and the
// added in the linked list, which
// are in the reversed order->
}
// UTILITY FUNCTIONS
/* Function to insert a node at the
beginning of the Doubly Linked List */
void Push(int new_data)
{
// Allocate node
Node* new_node =
new Node(new_data);
/* Since we are adding at the
beginning, prev is always NULL */
new_node->prev = NULL;
/* Link the old list off the
new node */
new_node->next = head;
/* Change prev of head node to
new node */
if (head != NULL)
{
head->prev = new_node;
}
/* Move the head to point to the
new node */
head = new_node;
}
/* Function to print nodes in a given
doubly linked list. This function is
same as printList() of singly linked list */
void printList(Node* node)
{
while (node)
{
cout << node->data << " ";
node = node->next;
}
}
};
// Driver Code
int main()
{
LinkedList list;
/* Let us create a sorted linked list
to test the functions Created linked
list will be 10->8->4->2 */
list.Push(2);
list.Push(4);
list.Push(8);
list.Push(10);
cout <<
"Original linked list " << endl;
list.printList(list.head);
list.reverse();
cout << endl;
cout <<
"The reversed Linked List is " << endl;
list.printList(list.head);
}
// This code is contributed by Pratham76
Producción
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
En este método, recorremos la lista enlazada una vez y agregamos elementos a la pila, y nuevamente recorremos el conjunto para actualizar todos los elementos. El todo toma 2n tiempo, que es la complejidad temporal de O(n).
Consulte el artículo completo sobre Invertir una lista doblemente vinculada para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA