Programa Javascript para invertir una lista doblemente enlazada

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.

<script>
// Javascript program to reverse a 
// doubly linked list
var head;
  
class Node 
{
    constructor(val) 
    {
        this.data = val;
        this.prev = null;
        this.next = null;
    }
}
      
/* Function to reverse a Doubly Linked List */
function reverse() 
{
    var temp = null;
    var current = head;
      
    /* 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 head, check for the cases 
       like empty list and list with only one node */
    if (temp != null) 
    {
        head = temp.prev;
    }
}
  
// UTILITY FUNCTIONS 
/* Function to insert a node at the beginning 
   of the Doubly Linked List */
function push(new_data) 
{
    // Allocate node 
    var 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 */
function printList(node) 
{
    while (node != null) 
    {
        document.write(node.data + " ");
        node = node.next;
    }
}
  
/* Let us create a sorted linked list to test 
   the functions Created linked list will be 
   10->8->4->2 */
push(2);
push(4);
push(8);
push(10);
  
document.write(
"Original linked list <br/>");
printList(head);
  
reverse();
document.write("<br/>");
document.write("The reversed Linked List is <br/>");
printList(head);
// This code is contributed by gauravrajput1
</script>

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:

1. Siga empujando los datos del Node en la pila. -> O(n)
2. Sigue sacando los elementos y actualizando la lista doblemente enlazada

<script>
// Javascript program to reverse a doubly 
// linked list
class Node 
{
    constructor(d)
    {
        this.data = d;
        this.next = this.prev = null;
    }
}
  
let head;
  
// Function to reverse a Doubly 
// Linked List using Stacks
function reverse()
{
    let stack = [];
    let temp = head;
      
    while (temp != null)
    {
        stack.push(temp.data);
        temp = temp.next;
    }
      
    // Added all the elements sequence 
    // wise in the stack
    temp = head;
      
    while (temp != null)
    {
        temp.data = stack.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 
function push(new_data)
{
      
    // Allocate node 
    let 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
function printList(node)
{
    while (node != null) 
    {
        document.write(node.data + " ");
        node = node.next;
    }
}
  
// Driver Code
  
// Let us create a sorted linked list 
// to test the functions Created linked
// list will be 10->8->4->2
push(2);
push(4);
push(8);
push(10);
  
document.write(
"Original linked list <br>");
printList(head);
  
reverse();
document.write("<br>");
document.write(
"The reversed Linked List is <br>");
printList(head);
// This code is contributed by rag2127
</script>

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.